11356017
Loop Transformations for Reducing Data Space Requirements of Resource-Constrained Applications
Embedded computing platforms are often resource constrained, requiring great design and implementation attention to memory, power and heat related parameters. An important task for a compiler in such platforms is to simplify the process of developing applications for limited memory devices and resource constrained clients. Focusing on array-intensive embedded applications, this work explores how loop-based compiler optimizations can be used for increasing memory location reuse. Our goal is to transform a given application in such a way that the resulting code has fewer cases (as compared to the original code) where the lifetimes of array elements overlap. The reduction in lifetimes of array elements can then be exploited by reusing memory locations as much as possible. Our results indicate that the proposed strategy reduces data space requirements of ten resource constrained applications by more than 40% on the average.
13530819
Exploiting last idle periods of links for network power management
Network power optimization is becoming increasingly important as the sizes of the data manipulated by parallel applications and the complexity of inter-processor data communications are continuously increasing. Several hardware-based schemes have been proposed in the past for reducing network power consumption, either by turning off unused communication links or by lowering voltage/frequency in links with low usage. While the prior research shows that these schemes can be effective in certain cases, they share the common drawback of not being able to predict the link active and idle times very accurately. This paper, instead, proposes a compiler-based scheme that determines the last use of communication links at each loop nest and inserts explicit link turn-off calls in the application source. Specifically, for each loop nest, the compiler inserts a turn-off call per communication link. Each turned-off link is reactivated upon the next access to it. We automated this approach within a parallelizing compiler and applied it to eight array-intensive embedded applications.
2552667
An evaluation of code and data optimizations in the context of disk power reduction
Disk power management is becoming increasingly important in high-end server and cluster type of environments that execute data-intensive applications. While hardware-only approaches (e.g., low-power modes supported by current disks) are successful to a certain extent, one also needs to consider the software side to achieve further energy savings. This paper first demonstrates that conventional data locality oriented code transformations are not sufficient for minimizing disk power consumption. The reason is that these optimizations do not take into account how disk-resident array data are laid out on the disk system, and consequently, fail to increase idle periods of disks, which is the primary metric using which disk power can be reduced. Instead, we propose a disk layout aware application optimization strategy that uses both code restructuring and data layout optimization. Our experimental evaluation with several benchmark codes reveal that the proposed strategy is very successful in reducing disk energy consumption without performing much worse than a pure data locality oriented scheme, as far as execution cycles are concerned. The experiments also show that the benefits coming from our approach increase with the increased number of disks; i.e., it scales very well.
17088807
Reducing NoC energy consumption through compiler-directed channel voltage scaling
While scalable NoC (Network-on-Chip) based communication architectures have clear advantages over long point-to-point communication channels, their power consumption can be very high. In contrast to most of the existing hardware-based efforts on NoC power optimization, this paper proposes a compiler-directed approach where the compiler decides the appropriate voltage/frequency levels to be used for each communication channel in the NoC. Our approach builds and operates on a novel graph based representation of a parallel program and has been implemented within an optimizing compiler and tested using 12 embedded benchmarks. Our experiments indicate that the proposed approach behaves better - from both performance and power perspectives - than a hardwarebased scheme and the energy savings it achieves are very close to the savings that could be obtained from an optimal, but hypothetical voltage/frequency scaling scheme.
17981801
Studying storage-recomputation tradeoffs in memory-constrained embedded processing
Fueled by an unprecedented desire for convenience and self-service, consumers are embracing embedded technology solutions that enhance their mobile lifestyles. Consequently, we witness an unprecedented proliferation of embedded/mobile applications. Most of the environments that execute these applications have severe power, performance, and memory space constraints that need to be accounted for. In particular, memory limitations can present serious challenges to embedded software designers. The current solutions to this problem include sophisticated packaging techniques and code optimizations for effective memory utilization. While the first solution is not scalable, the second one is restricted by intrinsic data dependences in the code that prevent code restructuring. In this paper, we explore an alternate approach for reducing memory space requirements of embedded applications. The idea is to re-compute the result of a code block (potentially multiple times) instead of storing it in memory and performing a memory operation whenever needed. The main benefit of this approach is that it reduces memory space requirements, that is, no memory space is reserved for storing the result of the code block in question.
7347899
Data compression for improving SPM behavior
Scratch-pad memories (SPMs) enable fast access to time-critical data. While prior research studied both static and dynamic SPM management strategies, not being able to keep all hot data (i.e., data with high reuse) in the SPM remains the biggest problem. This paper proposes data compression to increase the number of data blocks that can be kept in the SPM. Our experiments with several embedded applications show that our compression-based SPM management heuristic is very effective and outperforms prior static and dynamic SPM management approaches. We also present an ILP formulation of the problem, and show that the proposed heuristic generates competitive results with those obtained through ILP, while spending much less time in compilation.
206977606
Priority Based Overlay Multicast for Distributed Interactive Applications
Distributed Interactive Applications (DIAs) is different with other network-based applications, since the data should be delivered to the receiver node according to its priority. Among the existing overlay multicast protocols the "priority-based directed minimum spanning tree" (PST) is designed for DIAs. But in PST the available bandwidth (avail-bw) is used inefficiently and the system becomes unstable when its scale increases. This paper proposed a novel overlay multicast protocol named Priority Based Overlay Multicast (POM), which uses the entities’ priority, links’ delay and node’s avail-bw to build multicast tree. By using POM the nodes with high priority receive the data in short delay, while the nodes with low priority tolerate a long delay in order to balance the available bandwidth usage among the nodes. The simulation results show that POM uses the avail-bw efficiently and keeps the system stable when its scale increases. Keywords: DIAs; Priority; Available bandwidth.
30765152
On the Quickest Path Problem
Abstract Let N be an input network and σ be the amount of data to be transmitted. We present an O( mn 2 ) time algorithm that finds all-pairs quickest paths, for a given value of σ, and show that the quickest path between any two nodes for any value of σ can be found in O(log m ) time, provided O( mn 2 ) preprocessing time is spent.
15396672
Maintaining System State Information in a Multiagent Environment for Effective Learning
One fundamental issue in multiagent reinforcement learning is how to deal with the limited local knowledge of an agent in order to achieve effective learning. In this paper, we argue that this issue can be more effectively solved if agents are equipped with a consistent global view. We achieve this by requiring agents to follow an interacting protocol. The properties of the protocol are derived and theoretically analyzed. A distributed protocol that satisfies these properties is presented. The experimental evaluations are conducted for a well-known test-case (i.e., pursuit game) in the context of two learning algorithms. The results show that the protocol is effective and the reinforcement learning algorithms using it perform much better. key words: multiagent system, system state, distributed protocol, token ring
5887540
An Algorithm for Computing a New Normal Form for Dynamical Systems
We propose in this paper a new normal form for dynamical systems or vector fields which improves the classical normal forms in the sense that it is a further reduction of the classical normal forms. We give an algorithm for an effective computation of these normal forms. Our approach is rational in the sense that if the coefficients of the system are in a field K(which, in practice, is Q, R), so is the normal form and all computations are done inK . As a particular case, if the matrix of the linear part is a companion matrix then we reduce the dynamical system to a single differential equation. Our method is applicable for both the nilpotent and the non-nilpotent cases. We have implemented our algorithm in Maple V and obtained many examples of the further reduced normal forms up to some finite order.
6873995
Policy-driven data dissemination for context-aware applications
Context-aware pervasive-computing applications require continuous monitoring of their physical and computational environment to make appropriate adaptation decisions in time. The data streams produced by sensors, however, may overflow the queues on the dissemination path. Traditional flow-control and congestion-control policies either drop data or force the sender to pause. When the data sender is sensing the physical environment, however, a pause is equivalent to dropping data. Instead of arbitrarily dropping data that may contain important events, we present a policy-driven data dissemination service named PACK, based on an overlay-based infrastructure for efficient multicast delivery. PACK enforces application-specified policies that define how to discard or summarize data flows wherever queues overflow on the data path, notably at the mobile hosts where applications often reside. A key contribution of our approach is to uniformly apply the data-stream "packing" abstraction to queue overflow caused by network congestion, slow receivers, and temporary disconnection. We present experimental results and a detailed application study of the PACK service.