42109913
An efficient low-power binding algorithm in high-level synthesis
We propose an efficient binding algorithm for power optimization in high-level synthesis. In prior work, it has been shown that several binding problems for low-power can be formulated as multi-commodity flow problems (due to an iterative execution of data flow graph) and be solved optimally. However, since the multi-commodity flow problem is NP-hard, the application is limited to a class of small sized problems. To overcome the limitation, we address the problem of how we can effectively make use of the property of efficient flow computations in a network so that it is extensively applicable to practical designs while producing close-to-optimal results. To this end, we propose an efficient two-step algorithm, which (1) determines a feasible binding solution by partially utilizing the computation steps for finding a maximum flow of minimum cost in a network and then (2) refines it iteratively. Experiments with a set of benchmark examples show that the proposed algorithm saves the run time significantly while maintaining close-to-optimal bindings in most practical designs.
195882206
Memory layout techniques for variables utilizing efficient DRAM access modes in embedded system design
The delay of memory access is one of the major bottlenecks in embedded systems' performance. In software compilation, it is known that there are high variations in memory access delay depending on the ways of storing/retrieving the variables in code to/from the memories. In this paper, we propose an effective storage assignment technique for variables to maximize the use of memory bandwidth. Specifically, we study the problem of DRAM memory layout for storing the nonarray variables in code to achieve a maximum utilization of page and/or burst modes for the memory accesses. The contributions of our work are, for each of page and burst modes: (1) We prove that the problem is NP-hard; (2) We propose an exact formulation of the problem and efficient memory layout algorithms, called Solve-MLP for the page mode and Solve-MLB for the burst mode; From experiments with a set of benchmark programs, we confirm that our proposed techniques use on average 20.0% and 9.9% more page accesses and 54.0% and 86.6% more burst accesses than those by OFU (the order of first use) and the technique in P.R. Panda et al. (1997), respectively.
29679621
Binding Algorithm for Power Optimization Based on Network Flow Method
We propose an efficient binding algorithm for power optimization in behavioral synthesis. In prior work, it has been shown that several binding problems for low-power can be formulated as multi-commodity flow problems (due to an iterative execution of data flow graph) and be solved optimally. However, since the multi-commodity flow problem is NP-hard, the application is limited to a class of small sized problems. To overcome the limitation, we address the problem of how we can effectively make use of the property of efficient flow computations in a network so that it is extensively applicable to practical designs while producing close-to-optimal results. To this end, we propose a two-step procedure, which (1) determines a feasible binding solution by partially utilizing the computation steps for finding a maximum flow of minimum cost in a network and then (2) refines it iteratively. Experiments with a set of benchmark examples show that the proposed algorithm saves the run time significantly while maintaining close-to-optimal bindings in most practical designs.
34093275
Memory layout techniques for variables utilizing efficient DRAM access modes in embedded system design
The delay of memory access is one of the major bottlenecks in embedded systems' performance. In software compilation, it is known that there are high variations in memory access delay depending on the ways of storing/retrieving the variables in code to/from the memories. In this paper, we propose effective storage assignment techniques for variables to maximize the use of memory bandwidth. Specifically, we study the problem of DRAM memory layout for storing the nonarray variables in code to achieve a maximum utilization of page and/or burst modes for the memory accesses. The contributions of our work are, for each page and burst modes: 1) we prove that the problem is NP-hard and 2) we propose an exact formulation of the problem and efficient memory layout algorithms, called Solve-MLP for the page mode and Solve-MLB for the burst mode. From experiments with a set of benchmark programs, we confirm that our proposed techniques use on average 28.2% and 10.1% more page accesses and 82.9% and 107% more burst accesses than those by the order of first use and the technique of Panda et al. in Proc. Int. Conf. Computer-Aided Design, 1997, and Panda et al. in ACM Trans. Design Automation Electron. Syst., 1997, respectively.
5197608
Address assignment combined with scheduling in DSP code generation
One of the important issues in embedded system design is to optimize program code for the microprocessor to be stored in ROM. In this paper, we propose an integrated approach to the DSP address code generation problem for minimizing the number of addressing instructions. Unlike previous works in which code scheduling and offset assignment are performed sequentially without any interaction between them, our work tightly couples offset assignment problem with code scheduling to exploit scheduling on minimizing addressing instructions more effectively. We accomplish this by developing a fast but accurate two-phase procedure which, for a sequence of code schedules, finds a sequence of memory layouts with minimum addressing instructions. Experimental results with benchmark DSP programs show improvements of 13%--33% in the address code size over Solve-SOA/GOA [7].
14917866
Protected heap sharing for memory-constrained java environments
Multitasking is one of capabilities we often want to have in memory-constrained embedded systems. To support multiple address spaces within a small physical memory, a simple memory management frequently encounters the lack of available memory. Our paper presents an efficient heap memory management scheme that reduces memory footprints by adaptively sharing heaps among multiple tasks in JVM environments. We modified KVM from Sun Microsystems so that Java applications acquire or release heaps in a shared pool on an as-needed basis. To protect address spaces among tasks in the absence of virtual memory capabilities, we use memory protection units (MPUs) by incorporating them into our heap sharing scheme. Our experiments with J2ME MIDP applications show significant reductions by 33% on average, ranging from 6% to 50% in memory usage over the execution. The overheads of our scheme in garbage collection are kept low. The execution times in our scheme increase only by 0.2% on average.
4649924
WAF: wireless-adaptive fair scheduling for multimedia stream in time division multiplexed packet cellular systems
Cellular systems are designed to support voice service over the wireless channel but nowadays data-only networks such as cdma2000 1x EV-DO and high speed downlink packet access (HSDPA) are being deployed in the midst of evolution to the next generation wireless networks. Such systems become important because data services are essential in future wireless networks that are supposed to adopt the concept of all-IP to support integrated services. To increase the data transmission rate at downlink in cdma2000 1x EV-DO and HSDPA, the base station (BS) uses only a channel multiplexed by time division, not by code division. These systems use proportional fair scheduling to maximize throughput. While it is useful for non real time traffic, it does not provide appropriate QoS for real time services such as voice and video. Therefore we need to incorporate the multimedia QoS requirements into the design of a new scheduling algorithm. Our proposed wireless-adaptive fair scheduling (WAF) tries to allocate time slots with fair share according to the stream requirements considering the varying channel conditions to achieve good throughput. The simulation results show that our scheme can guarantee fair service and increase throughput by up to 41% compared to the purely fair (PF) scheduling scheme.
15526593
Low-energy off-chip SDRAM memory systems for embedded applications
Memory systems are dominant energy consumers, and thus many energy reduction techniques for memory buses and devices have been proposed. For practical energy reduction practices, we have to take into account the interaction between a processor and cache memories together with application programs. Furthermore, energy characterization of memory systems must be accurate enough to justify various techniques. In this article, we build an in-house energy simulator for memory systems that is accelerated by special hardware support while maintaining accuracy. We explore energy behavior of memory systems for various values of the processor and memory clock frequencies and cache configuration. Each experiment is performed with 24M instruction steps of real application programs to guarantee accuracy.The simulator is based on precise energy characterization of memory systems including buses, bus drivers, and memory devices by a cycle-accurate energy measurement technique. We characterize energy consumption of each component by an energy state machine whose states and transitions are associated with the dynamic and static energy costs, respectively. Our approach easily characterizes the energy consumption of complex SDRAMs. We divide and quantify energy components of main memory systems for high-level reduction. The energy simulator enables us to devise practical energy reduction schemes by providing the actual amount of reduction out of the total energy consumption in main memory systems. We introduce several practical energy reduction techniques for SDRAM memory systems and demonstrate energy reduction ratio over the SDRAM memory systems with commercial SDRAM controller chipsets. We classify the SDRAM memory systems into high-performance and mid-performance classes and achieve suitable system configurations for each class. For instance, a typical high-performance 32-bit, 64 MB SDRAM memory system consumes 19.6 mJ, 33.8 mJ, 35.4 mJ, and 37.0 mJ for 24M instructions of an MP3 decoder, a JPEG compressor, a JPEG decompressor, and an MPEG4 decoder, respectively. Our reduction scheme saves 12.7 mJ, 15.1 mJ, 15.5 mJ, and 14.8 mJ, and the reduction ratios are 64.8%, 44.6%, 43.8%, and 40.1%, respectively, without compromising execution speed.
16379329
Genetic fuzzy discretization with adaptive intervals for classification problems
We propose a genetic fuzzy discretization method for continuous numerical attributes. Traditional discretization methods categorize the continuous attributes into a number of bins. Because they are made on crisp discretization, there exists considerable information loss. Fuzzy discretization allows overlapping intervals and reflects linguistic classification. However, the number of intervals, the boundaries of intervals, and the degrees of overlapping are intractable to get optimized. We use a genetic algorithm to optimize these parameters. Experimental results showed considerable improvement on the classification accuracy over a crisp discretization and a typical fuzzy discretization.
154999
Identifying Sources of Opinions with Conditional Random Fields and Extraction Patterns
Recent systems have been developed for sentiment classification, opinion recognition, and opinion analysis (e.g., detecting polarity and strength). We pursue another aspect of opinion analysis: identifying the sources of opinions, emotions, and sentiments. We view this problem as an information extraction task and adopt a hybrid approach that combines Conditional Random Fields (Lafferty et al., 2001) and a variation of AutoSlog (Riloff, 1996a). While CRFs model source identification as a sequence tagging task, AutoSlog learns extraction patterns. Our results show that the combination of these two methods performs better than either one alone. The resulting system identifies opinion sources with 79.3% precision and 59.5% recall using a head noun matching measure, and 81.2% precision and 60.6% recall using an overlap measure.
253336
Parameter Optimization by a Genetic Algorithm for a Pitch Tracking System
The emergence of multimedia data in databases requires adequate methods for information retrieval. In a music data retrieval system by humming, the first stage is to extract exact pitch periods from a flow of signals. Due to the complexity of speech signals, it is difficult to make a robust and practical pitch tracking system. We adopt genetic algorithm in optimizing the control parameters for note segmentation and pitch determination. We applied the results to HumSearch, a commercialized product, as a pitch tracking engine. Experimental results showed that the proposed engine notably improved the performance of the existing engine in HumSearch.