Electrical & Computer Engineering Research Works

Permanent URI for this collectionhttp://hdl.handle.net/1903/1658

Browse

Author: search.filters.author.Bhattacharyya, Shuvra S.

Search Results

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    CASPER: An Integrated Energy-Driven Approach for Task Graph Scheduling on Distributed Embedded Systems
    (IEEE, 2005-07) Kianzad, Vida; Bhattacharyya, Shuvra S.; Qu, Gang
    For multiprocessor embedded systems, the dynamic voltage scaling (DVS) technique can be applied to scheduled applications for energy reduction. DVS utilizes slack in the schedule to slow down processes and save energy. Therefore, it is generally believed that the maximal energy saving is achieved on a schedule with the minimum makespan (maximal slack). Most current approaches treat task assignment, scheduling, and DVS separately. In this paper, we present a framework called CASPER (Combined Assignment, Scheduling, and PowER-management) that challenges this common belief by integrating task scheduling and DVS under a single iterative optimization loop via genetic algorithm. We have conducted extensive experiments to validate the energy efficiency of CASPER. For homogeneous multiprocessor systems (in which all processors are of the same type), we consider a recently proposed slack distribution algorithm (PDP-SPM) [3]: applying PDP-SPM on the schedule with the minimal makespan gives an average of 53.8% energy saving; CASPER finds schedules with slightly larger makespan but a 57.3% energy saving, a 7.8% improvement. For heterogeneous systems, we consider the power variation DVS (PV-DVS) algorithm [13], CASPER improves its energy efficiency by 8.2%. Finally, our results also show that the proposed single loop CASPER framework saves 23.3% more energy over GMA+EE-GLSA [12], the only other known integrated approach with a nested loop that combines scheduling and power management in the inner loop but leaves assignment in the outer loop.
  • Thumbnail Image
    Item
    Exploring the Probabilistic Design Space of Multimedia Systems
    (IEEE, 2003-06) Hua, Shaoxiong; Qu, Gang; Bhattacharyya, Shuvra S.
    In this paper, we propose the novel concept of probabilistic design for multimedia systems and a methodology to quickly explore such design space at an early design stage. The probabilistic design is motivated by the challenge of how to design, but not over-design, multimedia embedded systems while systematically incorporating such application’s performance requirements, uncertainties in execution time, and tolerance for reasonable execution failures. Our goal is to bridge the gap between real-time analysis and embedded software implementation for rapid and economic (multimedia) system prototyping. Our method takes advantage of multimedia system’s unique features mentioned above to relax the rigid hardware requirements for software implementation and eventually avoid over-designing the system.
  • Thumbnail Image
    Item
    Energy Reduction Techniques for Multimedia Applications with Tolerance to Deadline Misses
    (IEEE, 2003-06) Hua, Shaoxiong; Qu, Gang; Bhattacharyya, Shuvra S.
    Many embedded systems such as PDAs require processing of the given applications with rigid power budget. However, they are able to tolerate occasional failures due to the imperfect human visual/auditory systems. The problem we address in this paper is how to utilize such tolerance to reduce multimedia system’s energy consumption for providing guaranteed quality of service at the user level in terms of completion ratio. We explore a range of offline and on-line strategies that take this tolerance into account in conjunction with the modest non-determinism in application’s execution time. First, we give a simple best-effort approach that achieves the maximum completion ratio; then we propose an enhanced on-line best-effort energy minimization (BEEM) approach and a hybrid offline/on-line minimumeffort (O2ME) approach. We prove that BEEM maintains the maximum completion ratio while consuming the provably least amount of energy and O2ME guarantees the required completion ratio statistically. We apply both approaches to a variety of benchmark task graphs, most from popular DSP applications. Simulation results show that significant energy savings (38% for BEEM and 54% for O2ME, both over the simple best-effort approach) can be achieved while meeting the required completion ratio requirements.
  • Thumbnail Image
    Item
    Real-Time Memory Management: Compile-Time Techniques and Run-Time Mechanisms that Enable the Use of Caches in Real-Time Systems
    (2000-09) Jacob, Bruce; Bhattacharyya, Shuvra S.
    This paper demonstrates the intractability of achieving statically predictable performance behavior with traditional cache organizations (i.e., the real-time cache problem) and describes a non-traditional organization—combined hardware and software techniques—that can solve the real-time cache problem. We show that the task of placing code and data in the memory system so as to eliminate conflicts in traditional direct-mapped and set-associative caches is NP-complete. We discuss alternatives in both software and hardware that can address the problem: using address translation with software support can eliminate non-predicted conflict misses, and explicit management of the cache contents can eliminate non-predicted capacity misses. We present a theoretical analysis of the performance benefits of managing the cache contents to extend the effective size of the cache.