Browsing by Author "Bhattacharyya, Shuvra S."
Now showing 1 - 16 of 16
Results Per Page
Sort Options
Item Approximation Algorithms and Heuristics for the Dynamic Storage Allocation Problem(1999-06-08) Murthy, Praveen K.; Bhattacharyya, Shuvra S.In this report, we look at the problem of packing a number of arrays in memory efficiently. This is known as the dynamic storage allocation problem (DSA) and it is known to be NP-complete. We develop some simple, polynomial-time approximation algorithms with the best of them achieving a bound of 4 for a sub-class of DSA instances. We report on an extensive experimental study on the FirstFit heuristic and show that the average-case performance on random instances is within 7% of the optimal value. Also cross-referenced as UMIACS-TR-99-31Item CASPER: An Integrated Energy-Driven Approach for Task Graph Scheduling on Distributed Embedded Systems(IEEE, 2005-07) Kianzad, Vida; Bhattacharyya, Shuvra S.; Qu, GangFor 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.Item Contention-conscious transaction ordering in embedded multiprocessors systems(2000-03-28) Khandelia, Mukul; Bhattacharyya, Shuvra S.This paper explores the problem of efficiently ordering interprocessor communication operations in statically-scheduled multiprocessors for iterative dataflow graphs. In most digital signal processing applications, the throughput of the system is significantly affected by communication costs. By explicitly modeling these costs within an effective graph-theoretic analysis framework, we show that ordered transaction schedules can significantly outperform self-timed schedules even when synchronization costs are low. However, we also show that when communication latencies are non-negligible, finding an optimal transaction order given a static schedule is an NP-complete problem, and that this intractability holds both under iterative and non-iterative execution. We develop new heuristics for finding efficient transaction orders, and perform an experimental comparison to gauge the performance of these heuristics. (Also cross-referenced as UMIACS-TR-2000-09)Item Dataflow-based Design and Implementation of Image Processing Applications(2011-06-13) Shen, Chung-Ching; Plishker, William; Bhattacharyya, Shuvra S.Dataflow is a well known computational model and is widely used for expressing the functionality of digital signal processing (DSP) applications, such as audio and video data stream processing, digital communications, and image processing. These applications usually require real-time processing capabilities and have critical performance constraints. Dataflow provides a formal mechanism for describing specifications of DSP applications, imposes minimal data-dependency constraints in specifications, and is effective in exposing and exploiting task or data level parallelism for achieving high performance implementations. To demonstrate dataflow-based design methods in a manner that is concrete and easily adapted to different platforms and back-end design tools, we present in this report a number of case studies based on the lightweight dataflow (LWDF) programming methodology. LWDF is designed as a "minimalistic" approach for integrating coarse grain dataflow programming structures into arbitrary simulation- or platform-oriented languages, such as C, C++, CUDA, MATLAB, SystemC, Verilog, and VHDL. In particular, LWDF requires minimal dependence on specialized tools or libraries. This feature --- together with the rigorous adherence to dataflow principles throughout the LWDF design framework --- allows designers to integrate and experiment with dataflow modeling approaches relatively quickly and flexibly into existing design methodologies and processes.Item The DSPCAD Integrative Command Line Environment: Introduction to DICE Version 1(2009-11-23) Bhattacharyya, Shuvra S.; Kedilaya, Soujanya; Plishker, William; Sane, Nimish; Shen, Chung-Ching; Zaki, GeorgeDICE (the DSPCAD Integrative Command Line Environment) is a package of utilities that facilitates efficient management of software projects. Key areas of emphasis in DICE are cross-platform operation, support for projects that integrate heterogeneous programming languages, and support for applying and integrating different kinds of design and testing methodologies. The package is being developed at the University of Maryland to facilitate the research and teaching of methods for implementation, testing, evolution, and revision of engineering software. The package is also being developed as a foundation for developing experimental research software for techniques and tools in the area of computer-aided design (CAD) of digital signal processing (DSP) systems. The package is intended for cross-platform operation, and is currently being developed and used actively on the Windows (equipped with Cygwin), Solaris, and Linux platforms. This report provides an introduction to DICE, and provides background on some of the key features in DICE. This report also gives a brief introduction to dicelang, which is a plug-in package for DICE that provides additional utilities, libraries, and tools for managing software projects in specific programming languages.Item The DSPCAD Integrative Command Line Environment: Introduction to DICE Version 1.1(2011-06-13) Bhattacharyya, Shuvra S.; Plishker, William; Shen, Chung-Ching; Sane, Nimish; Zaki, GeorgeDICE (the DSPCAD Integrative Command Line Environment) is a package of utilities that facilitates efficient management of software projects. Key areas of emphasis in DICE are cross-platform operation, support for projects that integrate heterogeneous programming languages, and support for applying and integrating different kinds of design and testing methodologies. The package is being developed at the University of Maryland to facilitate the research and teaching of methods for implementation, testing, evolution, and revision of engineering software. The package is also being developed as a foundation for developing experimental research software for techniques and tools in the area of computeraided design (CAD) of digital signal processing (DSP) systems. The package is intended for cross-platform operation, and is currently being developed and used actively on the Linux, Mac OS, Solaris, and Windows (equipped with Cygwin) platforms. This report provides an introduction to DICE, and provides background on some of the key features in DICE Version 1.1. This report also gives a brief introduction to dicelang, which is a plug-in package for DICE that provides additional utilities, libraries, and tools for managing software projects in specific programming languages.Item The DSPCAD Lightweight Dataflow Environment: Introduction to LIDE Version 0.1(2011-10-21) Shen, Chung-Ching; Wang, Lai-Huei; Cho, Inkeun; Kim, Scott; Won, Stephen; Plishker, William; Bhattacharyya, Shuvra S.LIDE (the DSPCAD Lightweight Dataflow Environment) is a flexible, lightweight design environment that allows designers to experiment with dataflow-based approaches for design and implementation of digital signal processing (DSP) systems. LIDE contains libraries of dataflow graph elements (primitive actors, hierarchical actors, and edges) and utilities that assist designers in modeling, simulating, and implementing DSP systems using formal dataflow techniques. The libraries of dataflow graph elements (mainly actors) contained in LIDE provide useful building blocks that can be used to construct signal processing applications, and that can be used as examples that designers can adapt to create their own, customized LIDE actors. Furthermore, by using LIDE along with the DSPCAD Integrative Command Line Environment (DICE), designers can efficiently create and execute unit tests for user-designed actors. This report provides an introduction to LIDE. The report includes details on the process for setting up the LIDE environment, and covers methods for using pre-designed libraries of graph elements, as well as creating user-designed libraries and associated utilities using the C language. The report also gives an introduction to the C language plug-in for dicelang. This plug-in, called dicelang-C, provides features for efficient C-based project development and maintenance that are useful to apply when working with LIDE.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.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.Item The Hierarchical Timing Pair Model for Synchronous Dataflow Systems(2000-11-16) Chandrachoodan, Nitin; Bhattacharyya, Shuvra S.; Liu, K. J. RayWe consider the problem of representing timing information associated with functions in a dataflow graph. This information is used for behavioral synthesis of appropriate architectures for implementing the graph. Conventional models for timing suffer from shortcomings that make it difficult to easily represent timing information in a hierarchical manner, especially for multirate systems. We identify some of these shortcomings, and provide an alternate timing model for hardware implementations that does not have these problems. This model is capable of providing a unified view of hierarchical combinational and sequential circuits under the assumptions of high-level scheduling. The resulting compact representation of the timing information can be used to streamline system performance analysis. We show that with some reasonable assumptions on the way hardware implementations of multirate systems operate, we can derive general hierarchical descriptions of multirate systems in a similar manner to single sample-rate systems. Several analytical results that previously applied only to single sample-rate systems can also easily be extended to multirate systems under the new assumptions. We have applied our model to several signal processing applications, and obtained favorable results. We present an algorithm to compute the timing parameters, and have used this to compute timing parameters for a number of benchmarks circuits. We present the results obtained on several ISCAS benchmark circuits and also several multirate dataflow graphs corresponding to useful signal processing applications. (Also cross-referenced as UMIACS-TR-2000-75)Item Negative Cycle Detection in Dynamic Graphs(1999-10-01) Chandrachoodan, Nitin; Bhattacharyya, Shuvra S.; Liu, K.J.RayWe examine the problem of detecting negative cycles in a dynamic graph, which is a fundamental problem that arises in electronic design automation and systems theory. Previous approaches used for this have tried to modify Dijkstra's algorithm since it is the fastest known Single-Source Shortest Path algorithm. We introduce the concept of {\em batch mode} negative cycle detection, in which a graph changes over time, and negative cycle detection needs to be done periodically. Such scenarios arise, for example, during iterative design space exploration for hardware and software synthesis. We present an algorithm for this problem, based on the Bellman-Ford algorithm, which outperforms previous approaches. We also show that this technique leads to very fast algorithms for the computation of the maximum-cycle mean (MCM) of a graph, especially for a certain form of {\em sparse graph}. Such sparseness often occurs in practice, as demonstrated for example by the ISCAS 89/93 benchmarks. We present experimental results that demonstrate the advantages of our batch-processing techniques, and illustrate their application to design-space exploration by developing an automated local-search technique for multiple-voltage scheduling of iterative data-flow graphs. (Also cross-referenced as UMIACS-TR-99-59)Item Parameterized Looped Schedules(2006-01-13T19:45:06Z) Ko, Ming-Yung; Zissulescu, Claudiu; Puthenpurayil, Sebastian; Nasr, Rami; Bhattacharyya, Shuvra S.; Kienhius, Bart; Deprettere, EdThis paper is concerned with the compact representation of execution sequences in terms of efficient looping constructs. Here, by a looping construct we mean a compact way of specifying a finite repetition of a set of execution primitives (“instructions”). Such compaction, which can be viewed as a form of hierarchical run-length encoding, has application in many embedded software contexts, including efficient control generation for Kahn processes, and software synthesis for static dataflow models of computation, such as synchronous dataflow and cyclo-static dataflow. In this paper, we significantly generalize previous models for loop-based code compaction of DSP programs to yield a configurable code compression methodology that exhibits a broad range of achievable trade-offs. Specifically, we formally develop and apply to DSP hardware and software implementation a parameterizable loop scheduling approach with compact format, dynamic reconfigurability, and low overhead decompression.Item Parameterized Modeling and Scheduling of Dataflow Graphs(1999-12-03) Bhattacharya, Bishnupriya; Bhattacharyya, Shuvra S.There is no abstract available. (Also cross-referenced as UMIACS-TR-99-73)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.Item Shared Memory Implementations of Synchronous Dataflow Specifications Using Lifetime Analysis Techniques(1999-06-08) Murthy, Praveen K.; Bhattacharyya, Shuvra S.There has been a proliferation of block-diagram environments for specifying and prototyping DSP systems. These include tools from academia like Ptolemy [6], and commercial tools like SPW from Cadence Design Systems, and Cossap from Synopsys. The block diagram languages used in these environments are usually based on dataflow semantics because various subsets of dataflow have proven to be good matches for expressing and modeling signal processing systems. In particular, synchronous dataflow (SDF)[14] has been found to be a particularly good match for expressing multirate signal processing systems [5]. One of the key problems that arises during synthesis from an SDF specification is scheduling. Past work on scheduling [3] from SDF has focused on optimization of program memory and buffer memory. However, in [3], no attempt was made for overlaying or sharing buffers. In this paper, we formally tackle the problem of generating optimally compact schedules for SDF graphs, that also attempt to minimize buffering mem- ory under the assumption that buffers will be shared. This will result in schedules whose data memory usage is drastically lower than methods in the past have achieved. The method we use is that of lifetime analysis; we develop a model for buffer lifetimes in SDF graphs, and develop scheduling algorithms that attempt to generate schedules that minimize the maximum number of live tokens under the particular buffer lifetime model. We develop several efficient algorithms for extracting the relevant lifetimes from the SDF schedule. We then use the firstfit heuristic for packing arrays efficiently into memory. We report extensive experimental results on applying these techniques to several practical SDF systems, and show improvements that average 50% over previous techniques, with some systems exhibiting upto an 83% improvement over previous techniques. Also cross-referenced as UMIACS-TR-99-32Item Using the DSPCAD Integrative Command-Line Environment: User's Guide for DICE Version 1.1(2011-06-23) Bhattacharyya, Shuvra S.; Shen, Chung-Ching; Plishker, William; Sane, Nimish; Zaki, GeorgeThis document provides instructions on setting up, starting up, and building DICE and its key companion packages, dicemin and dicelang. This installation process is based on a general set of conventions, which we refer to as the DICE organizational conventions, for software packages. The DICE organizational conventions are specified in this report. These conventions are applied in DICE, dicemin, and dicelang, and also to other software packages that are developed in the Maryland DSPCAD Research Group.