Catálogo de publicaciones - libros

We consider non-preemptively scheduling a bag of independent mixed tasks in computational grids. We construct a novel Generalized Distributed Scheduler () for tasks with different priorities and deadlines. Tasks are ranked based upon priority and deadline and scheduled. Tasks are shuffled to earlier points to pack the schedule and create fault tolerance. Dispatching is based upon task-resource matching and accounts for computation as well as communication capacities. Simulation results demonstrate that with respect to the number of high-priority tasks meeting deadlines, outperforms prior approaches by over 40% without degrading schedulability of other tasks. Indeed, with respect to the total number of schedulable tasks meeting deadlines, outperforms them by 4%. The complexity of is where is the number of tasks and the number of machines. successfully schedules tasks with hard deadlines in a mix of soft and firm tasks, without a knowledge of a complete state of the grid. This way it helps open the grid and makes it amenable for commercialization.

In this paper, we propose a heuristic static energy-aware scheduling algorithm for scheduling tasks with precedence constraints on a heterogeneous multiprocessor embedded system consisting of processing elements equipped with dynamic voltage scaling capabilities. While most energy-aware scheduling algorithms in the literature assume that the mapping of the tasks to the processors is known and consider only task ordering and voltage scaling, our algorithm takes into consideration all three factors using the concept of energy gradient. Higher values of energy gradient result in larger reduction in the energy consumption together with smaller increase in the makespan of the schedules. We compare our algorithm to a genetic algorithm in the literature and show that although our algorithm does not consider intra-task voltage scaling, it still provides an average energy savings of about 4% while reducing the optimization time by more than 93%. These energy savings are more significant for larger task graphs.

Power-aware operating systems/processor controllers ensure that the system temperature does not exceed a threshold by utilizing system-throttling, where the clock speed is scaled to an equilibrium load. We denote this as the Constant policy, and compare against Zig-Zag policies that alternate between phases of cooling and heating. In this paper, we characterize and calculate the best possible Zig-Zag policy, and argue that simple system-throttling rules are often optimal.

In reality, however, the system design often forces us to implement Zig-Zag policies. In particular, we consider the case where the processor can operate only at a few discrete states; thus it is required to alternate between cooling and heating phases. In such a setting, we develop an algorithm that outperforms all other Zig-Zag policies, and present computational experiments emphasizing the performance of our algorithm.

As feature size shrinks, the dominant component of power consumption will be leakage. As caches represent a considerable fraction of area for many platforms, from embedded to highly paralleled systems, cache leakage control continues to become a critical issue. Drowsy cache technique is a state-preserving technique which reduces leakage by pulling down the voltages on selected lines. To exploit the temporal locality present in the data stream, existing drowsy cache policies update drowsy/active mode after an execution window of fixed clock cycles, which lack the flexibility to adapt to program behavior. We introduce a tri-mode FSM control policy, which exploits global information and tries to keep a small set of lines in active for future references, after each distinct line references. This based policy well adapts to the temporal locality, steadily delivers better energy savings with similar performance overhead, is simple to implement, and places an upper bound on leakage power.

With the increased complexity of platforms coupled with data centers’ servers sprawl, power consumption is reaching unsustainable limits. Memory is an important target for platform-level energy efficiency, where most power management techniques use multiple power state DRAM devices to transition them to low-power states when they are “sufficiently” idle. However, fully-interleaved memory in high-performance servers presents a research challenge to the memory power management problem. Due to data striping across all memory modules, memory accesses are distributed in a manner that considerably reduces the idleness of memory modules to warrant transitions to low-power states. In this paper we introduce a novel technique for dynamic memory interleaving that is adaptive to incoming workload in a manner that reduces memory energy consumption while maintaining the performance at an acceptable level. We use optimization theory to formulate and solve the power-performance management problem. We use dynamic cache line migration techniques to increase the idleness of memory modules by consolidating the application’s working-set on a minimal set of ranks. Our technique yields energy saving of about 48.8 % (26.7 kJ) compared to traditional techniques measured at 4.5%. It delivers the maximum performance-per-watt during all phases of the application execution with a maximum performance-per-watt improvement of 88.48%.

We present a new set of distributed algorithms for scheduling sensors to enhance the total lifetime of a wireless sensor network. These algorithms are based on constructing minimal cover sets each consisting of one or more sensors which can collectively cover the local targets.  Some of the covers are heuristically better than others for a sensor trying to decide its own sense-sleep status.  This leads to various ways to assign priorities to the covers. The algorithms work by having each sensor transition through these possible prioritized cover sets, settling for the best cover it can negotiate with its neighbors.   A local lifetime dependency graph consisting of the cover sets as nodes with any two nodes connected if the corresponding covers intersect captures the interdependencies among the covers. We present several variations of the basic algorithmic framework.  The priority function of a cover is derived from its degree or connectedness in the dependency graph - usually lower the better.  Lifetime improvement is 10% to 20% over the existing algorithms, while maintaining comparable communication overheads.   We also show how previous algorithms can be formulated within our framework.

Asynchronous power efficient communication protocols are crucial to the success of wireless sensor networks (WSNs) as a distributed computing paradigm. This paper presents an improved asynchronous duty-cycled MAC protocol for WSN. It adopts a novel dual preamble sampling (DPS) approach by combining low power listening (LPL) with short strobed preambles to significantly reduce idle listening in existing protocols. In our ns-2 based experiments, the performance of the proposed solution is compared with B-MAC and X-MAC, two most recent and popular asynchronous MAC protocols for WSNs. Depending on the traffic load and preamble length, the proposed DPS-MAC improves energy consumption significantly compared to X-MAC without degrading other network performances such as delivery ratio and latency. For example for the traffic rate of 0.1 packets/s and preamble length of 0.1s, the average improvement in energy consumption compared to X-MAC is about 154%.

Traditionally, an instruction decoder is designed as a monolithic structure that inhibit the leakage energy optimization. In this paper, we consider a split instruction decoder that enable the leakage energy optimization. We also propose a compiler scheduling algorithm that exploits instruction slack to increase the simultaneous active and idle duration in instruction decoder. The proposed compiler-assisted scheme obtains a further 14.5% reduction of energy consumption of instruction decoder over a hardware-only scheme for a VLIW architecture. The benefits are 17.3% and 18.7% in the context of a 2-clustered and a 4-clustered VLIW architecture respectively.

This paper presents our work in combining peer-to-peer dynamic tree management with hierarchical Operational Transformation (OT) over document trees to achieve low computational and communication costs. We discuss our approach in storing the document tree in a peer-to-peer, distributed manner and maintaining convergence, causality preservation, and intention preservation (CCI) via a peer-to-peer caching system. Because changes are sent to other users within the system only as needed (and cached when possible), our approach minimizes communication costs among multiple readers and writers. Our algorithms balance the traffic and computational load among peers. They ensure that users always have the most current/correct copy of the section(s) of the document which they are viewing. Our approach outperforms existing OT techniques that broadcast messages and compute OT for each operation at all peers. This paper presents our algorithms and simulation results demonstrating the efficiencies and load balancing among peers within the system.

Flooding is a fundamental building block of unstructured peer-to-peer (P2P) systems. In this paper, we investigate techniques to improve the performance of flooding. In particular, we present , a novel semi-structured P2P architecture with bounded peer degree. Clustella decomposes the network into different clusters, allowing peers to quickly find those neighbors which contribute much to their routing efficiency. By its link selection strategy, Clustella achieves a good performance in static and dynamic environments.