This paper presents an energy-driven memory management methodology for the system-level exploration of hierarchical storage organizations. Starting from the behavioral specification of a data-intensive signal processing application, the memory management tasks are addressed in a common algebraic framework, using data-dependence analysis techniques similar to those used in modern compilers. This paper focuses on the data assignment to the memory layers and, then, on the signal-to-memory mapping, the target being the reduction of the energy consumption in the hierarchical memory subsystem.

Hierarchical memory organizations are used in embedded systems to reduce energy consumption and improve performance by assigning the frequently-accessed data to the low levels of memory hierarchy. Within a given level of hierarchy, energy and access times can be further reduced by memory banking. This paper addresses the problem of banking optimization, presenting a dynamic programming approach that takes into account all three major design objectives - energy consumption, performance, and die area, letting the designers decide on their relative importance for a specific project. The time complexity is independent of the size of the storage access trace and of the memory size - a significant advantage in terms of computation speed when these two parameters are large.

Partitioning a memory into multiple banks that can be independently accessed is an approach mainly used for the reduction of the dynamic energy consumption. When leakage energy comes into play as well, the idle memory banks must be put in a low-leakage `dormant' state to save static energy when not accessed. The energy savings must be large enough to compensate the energy overhead spent by changing the bank status from active to dormant, then back to active again. This paper addresses the problem of energy-aware on-chip memory banking, taking into account - during the exploration of the search space - the idleness time intervals of the data mapped into the memory banks. As on-chip storage, we target scratch-pad memories (SPMs) since they are commonly used in embedded systems as an alternative to caches. The proposed approach proved to be computationally fast and very efficient when tested for several data-intensive applications, whose behavioral specifications contain multidimensional arrays as main data structures.

This paper presents an energy-aware electronic design automation (EDA) methodology for the system-level exploration of hierarchical storage organizations, focusing mainly on data-intensive signal processing applications. Starting from the high-level behavioral specification of a given application, several memory management tasks are addressed in a common algebraic framework, using data-dependence analysis techniques similar to those used in modern compilers. Within this memory management software system, the designer can explore different algorithmic specifications functionally equivalent, by computing their minimum storage requirements. The system can perform an exploration based on energy consumption of signal assignments to the off- and on-chip memory layers, followed by a storage-efficient mapping of signals to the physical memories. The last phase of the methodology is an exploration approach for energy-aware banking of the on-chip memory, which takes into account both the static and dynamic energy consumption.

Many signal processing systems, particularly in the multimedia and telecom domains, are synthesized to execute data-dominated applications. In such systems, data transfer and storage have a significant impact on both the system performance and the major cost parameters - power consumption and chip area. This paper presents a software tool for system-level exploration, where several memory management tasks are addressed in a common theoretical framework. The tool can compute the minimum storage requirement of a given application and can produce the graph of storage variation during the code execution; it offers memory allocation and signal assignment solutions both for flat and hierarchical organizations and optimizes the dynamic energy consumption in the memory subsystem.

Many signal processing systems are synthesized to execute data-dominated applications. Their behavior is described in a high-level programming language, where the code is typically organized in sequences of loop nests and the main data structures are multidimensional arrays. Since data transfer and storage have a significant impact on both the system performance and the major cost parameters - power consumption and chip area, the designer must spend a significant effort during the system development process on the exploration of the memory subsystem in order to achieve a cost-optimized design. This paper focuses on the reduction of the dynamic energy consumption in the hierarchical memory subsystem of multidimensional signal processing systems, starting from the high-level behavioral specification of the application. The paper presents an algorithm which identifies those parts of arrays from a high-level specification that are intensely accessed (for read and/or write operations), whose storage on-chip yields the highest benefit in terms of dynamic energy consumption. Tested on a two-layer memory hierarchy (scratch-pad and off-chip memories), this algorithm led to significant savings of energy in comparison to previous computation models.

The storage requirements of the array-dominated and loop-organized algorithmic specifications running on embedded systems can be significant. Employing a data memory space much larger than needed has negative consequences on the energy consumption, latency, and chip area. Finding an optimized storage of the usually large arrays from these algorithmic specifications is an essential task of memory allocation. This paper proposes an efficient algorithm for mapping multidimensional arrays to the data memory. Similarly to [1], it computes bounding windows for live elements in the index space of arrays, but this algorithm is several times faster. More important, since this algorithm works not only forentirearrays, but alsopartsof arrays - like, for instance, array references or, more general, sets of array elements represented by lattices [2], this signal-to-memory mapping technique can be also applied in hierarchical memory architectures.

The storage requirements in data-intensive multidimensional signal processing systems have a significant impact on the system performance as well as on essential design parameters, like the overall power consumption and chip area. This paper addresses the problem of efficiently mapping the multidimensional signals from the algorithmic specification of the system into the physical memory. Different from all the previous mapping models that aim to optimize the memory sharing between the elements of a same array, this proposed assignment algorithm takes also into account the possibility of memory sharing between different arrays. As a consequence, the experiments with this novel signal-to-memory mapping approach exhibit important savings of data storage resulted after mapping.

The storage requirements in data-dominant signal processing systems, whose behavior is described by array-based, loop-organized algorithmic specifications, have an important impact on the overall energy consumption, data access latency, and chip area. Finding the optimal storage of the usually large arrays from these behavioral specifications is an important step during memory allocation. This paper proposes more efficient algorithms for the intra-array storage mapping models of De Greef (De Greef, et al., 1997) and Troncon (Troncon, et al., 2002), resulting in an implementation several time faster than the original ones.

The storage requirements of the array-dominated and loop-organized algorithmic specifications running on embedded systems can be significant. Employing a data memory space much larger than needed has negative consequences on the energy consumption, latency, and chip area. Finding an optimized storage of the usually large arrays from these algorithmic specifications is an important step during memory allocation. This paper proposes an efficient algorithm for mapping multi-dimensional arrays to the data memory. Similarly presented in R. Toncon et al., 2002, it computes bounding windows for live elements in the index space of arrays, but this algorithm is several times faster. Moreover, since this algorithm works not only for entire arrays, but also parts of arrays-like, for instance, array references or, more general, sets of array elements represented by lattices (Schrijver, 1986), this signal-to-memory mapping technique can be also applied in multi-layer memory hierarchies

The amount of the data storage in signal processing systems, whose behavior is described by loop-organized algorithmic specifications, has an important impact on the overall energy consumption, chip area, as well as system performance. This paper presents a non-scalar approach for computing the minimum storage requirements in high-level procedural specifications, where the main data structures are multi-dimensional arrays. This methodology uses both algebraic techniques specific to the data-flow analysis used in modern compilers and, also, more recent advances in the theory of polyhedra. In contrast with all the previous works which are only estimation methods, this approach can perform the exact computation of the minimum data storage even for applications with numerous loop nests and complex array references.

The storage requirements in data-intensive signal processing systems (including applications in video and image processing, artificial vision, medical imaging, real-time 3-D rendering, advanced audio and speech coding) have an important impact on both the system performance and the essential design parameters — the overall power consumption and chip area. This is due to the significant amount of data that must be stored during the execution of the algorithmic specifi- cation, as well as due to the amount of data transfers to/from large, energy-consuming, off-chip data memories. This paper addresses the problem of efficiently mapping the multidimensional signals from the algorithmic specification of the system into the physicalmemory. Different fromall the previous mapping models that aim to optimize the memory sharing between the elements of a same array, creating separate windows in the physical memory for distinct arrays, this proposed mapping model is the first one to exploit the possibility of memory sharing between different arrays. As a consequence, this signalto- memory mapping approach yields significant savings in the amount of data storage resulted after mapping.

This paper presents an improved topological algorithm for device-level analog placement with symmetry constraints. Based on the exploration of symmetric-feasible sequence-pairs (Balasa and Lampaert, 2000), the technique employs an efficient model of priority queue (Johnson, 1982). The use of this data structure entails a complexity of O (G middot n log log n) for each code evaluation, where n and G are the numbers of devices and symmetry groups, which is better than the complexity of other existent topological placement algorithms supporting symmetry constraints. The computation times exhibited by this approach are significantly better than those of the algorithms using an exploration strategy based on the absolute representation, as well as those of other previous topological algorithms.

Many integrated circuit systems, particularly in the multimedia and telecom domains, are inherently data dominant. For this class of systems, a large part of the power consumption is due to the data storage and data transfer. Moreover, a significant part of the chip area is occupied by memory. The computation of the memory size is an important step in the system-level exploration, in the early stage of designing an optimized (for area and/or power) memory architecture for this class of systems. This paper presents a novel nonscalar approach for computing exactly the minimum size of the data memory for high-level procedural specifications of multidimensional signal processing applications. In contrast with all the previous works which are estimation methods, this approach can perform exact memory computations even for applications with numerous and complex array references, and also with large numbers of scalars

The storage requirements in data-dominant signal processing systems, whose behavior is described by arraybased, loop-organized algorithmic specifications, have an important impact on the overall energy consumption, data access latency, and chip area. Applying different loop transformations on the specification code can significantly enhance the memory management of such VLSI systems, improving all the major parameters of the design space - power, area, and performance. This paper gives a global view on existing and recently proposed memory size evaluation approaches for procedural and non-procedural specifications. Moreover, it discusses typical memory management trade-offs taken into account during the exploration of system specifications by loop transformations, that can exploit these early size evaluations.

In real-time multimedia processing systems a very large part of the power consumption is due to the data storage and data transfer. Moreover, the area cost is often largely dominated by the memory modules. The computation of the memory size is an important step in the process of designing an optimized (for area and/or power) memory architecture for multimedia processing systems. This paper presents a novel non-scalar approach for computing exactly the memory size in real-time multimedia algorithms. This methodology uses both algebraic techniques specific to the data-flow analysis used in modern compilers, and also recent advances in the theory of integral polyhedra. In contrast with all the previous works which are only estimation methods, this approach performs exact memory computations even for applications with a large number of scalar signals

In real-time data-dominated communication and multimedia processing applications, due to the manipulation of large sets of data, a multi-layer memory hierarchy is used to enhance the system performance and also to reduce the energy consumption. Savings of dynamic energy can be obtained by accessing frequently used data from smaller memories rather than from large background memories. The optimization of the hierarchical memory architecture implies the addition of layers of smaller memories to which heavily used data can be copied. This paper presents a formal model for data reuse analysis which identifies those parts of arrays more intensely accessed, taking also into account the relative lifetimes of the signals. Tested on a two-layer memory hierarchy, this model led to savings in the dynamic energy from 40% to over 70% relative to the energy used in the case of a flat memory design.

The traditional way of approaching placement problems in computer-aided design (CAD) tools for analog layout is to explore an extremely large search space of feasible or unfeasible placement configurations, where the cells are moved in the chip plane (being even allowed to overlap in possibly illegal ways) by a stochastic optimizer. This paper presents a novel exploration technique for analog placement operating on a subset of tree representations of the layout-called symmetric-feasible, where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the search of the solution space. The computation times exhibited by this novel approach are significantly better than those of the algorithms using the traditional exploration strategy. This superior efficiency is partly due to the use of segment trees, a data structure introduced by Bentley, mainly used in computational geometry.

The traditional way of approaching device-level placement problems for analog layout is to explore a huge search space of absolute placement representations, where cells are allowed to illegally overlap during their moves [3, 10]. This paper presents a novel exploration technique for analog placement, operating on the set of tree representations of the layout [6, 2], where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the search of the solution space. The efficiency of the novel approach is due to the use of red-black interval trees [4], data structures employed to support operations on dynamic sets of intervals.

The traditional way of approaching device-level placement problems for analog layout is to explore a huge search space of absolute placement representations, where cells are allowed to illegally overlap during their moves (J. Cohn et al., Analog Device-Level Automation, Kluwer Acad. Publ., 1994; K. Lampaert et al., IEEE J. Solid-State Circ., vol. SC-30, no. 7, pp. 773-780, 1995; E. Malavasi et al., IEEE Trans. CAD, vol. 15, no. 8, pp. 923-942, 1996). This paper presents a novel analog placement technique operating on the set of binary tree representations of the layout (Y.C. Chang et al., Proc. 87th ACM/IEEE Des. Aut. Conf., pp. 458-463, 2000), where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the exploration of the solution space. The efficiency of the novel approach is due to a data structure called segment tree, mainly used in computational geometry.

Layout design for analog circuits has historically been a time consuming error-prone, manual task. Its complexity results not so much from the number of devices, as from the complex interactions among devices, as from the complex interactions among devices or with the operating environment, and also from continuous-valued performance specifications. This paper addresses the problem the device-level placement for analog layout in a non-traditional way. Different from the traditional approaches -exploring a huge search space with a combinatorial optimization technique, where the cells are represented by means of absolute coordinates, being allowed to illegally overlap during their moves in the chip plane - this paper advocates the use of non-slicing topological representations, like (symmetric-feasible) sequence-pairs, ordered- and binary- trees. Extensive tests, processing industrial analog designs, have shown that using skillfully the symmetry constraints (very typical to analog circuits) to remodel the solution space of the encoding systems, the topological representation techniques can achieve a better computation speed than the traditional approach, while obtaining a similar high quality of the designs.

Article Share on Solving large scale assignment problems in high-level synthesis by approximative quadratic programming Authors: Florin Balasa University of Illinois at Chicago, Dept. EECS, Chicago, IL University of Illinois at Chicago, Dept. EECS, Chicago, ILView Profile , Werner Geurts Target Compiler Technologies, Leuven, B-3001, Belgium Target Compiler Technologies, Leuven, B-3001, BelgiumView Profile , Francky Catthoor Interuniv. Microelectronics Center, Katholieke Universiteit Leuven Interuniv. Microelectronics Center, Katholieke Universiteit LeuvenView Profile , Hugo De Man Interuniv. Microelectronics Center, Katholieke Universiteit Leuven Interuniv. Microelectronics Center, Katholieke Universiteit LeuvenView Profile Authors Info & Claims GLSVLSI '01: Proceedings of the 11th Great Lakes symposium on VLSIMarch 2001 Pages 19–24https://doi.org/10.1145/368122.368149Online:01 March 2001Publication History 1citation163DownloadsMetricsTotal Citations1Total Downloads163Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The ordered tree (O-tree) representation has recently gained much interest in layout design automation. Different from previous topological representations of non-slicing floorplans, the O-tree representation is simpler, needs linear computation effort to generate a corresponding layout, and exhibits a smaller upper-bound of possible configurations. This paper addresses the problem of handling symmetry constraints in the context of the O-tree representation. This problem arises in analog placements, where symmetry is often used to match layout-induced parasitics and to balance thermal couplings in differential circuits. The good performance of our placement tool dealing with several analog designs taken from industry proves the effectiveness of our technique.

Several novel topological representations of non-slicing floorplans have been more recently proposed, providing new ideas and techniques for solving block placement problems and other related layout applications. Among these topological representations, ordered trees exhibit a lower redundancy and, therefore, a provable smaller search space, which makes them the best topological candidate for solving general block placement problems. Starting from the early eighties, binary trees have been widely used to represent slicing floorplans. This paper shows that binary trees can efficiently model non-slicing floorplans as well, as there is a one-to-one mapping between the sets of binary and ordered trees representing the floorplan. Moreover, this paper shows that binary trees exhibiting a certain property can be used to represent block placement configurations with symmetry constraints, which is very useful when dealing with device-level placement problems for analog layout. As the number of these trees is proven to be smaller than the number of symmetric-feasible sequence-pairs, using binary trees is better than using either sequence-pairs or O-trees when solving analog placement problems. A comparative evaluation, substantiating these theoretical results, has been carried out by providing alternative optimization engines to a placement tool operating in an industrial environment.

This paper addresses the problem of device-level placement for analog layout, focusing mainly on symmetry-related aspects. Different from most of the existent analog placement approaches, employing basically simulated annealing optimization algorithms operating on flat (absolute) spatial representations, our model uses a more recent topological representation called sequence-pair, which has the advantage of not being restricted to slicing floorplan topologies. In this paper, we explain how specific features essential to analog placement, such as the ability to deal with complex symmetry constraints (for instance, an arbitrary number of symmetry groups of cells), can be easily handled by employing the sequence-pair representation. Several analog examples substantiate the effectiveness of our placement tool, which is already in use in an industrial environment.

This paper addresses the problem of device-level placement for analog layout.Different from most of the existent approaches employing basically simulated annealing optimization algorithms operating on flat Gellat-Jepsen spatial representations [2], we are using a more recent topological representation called sequence-pair [7], which has the advantage of not being restricted to slicing floorplan topologies.In this paper, we are explaining how specific features essential to analog placement, as the ability to deal with symmetry and device matching constraints, can be easily handled by employing the sequence-pair representation.Several analog examples substantiate the effectiveness of our placement tool, which is already in use in an industrial environment.

Image and video processing applications involve large multidimensional signals which have to be stored in memory modules. In application-specific architectures for real-time multidimensional signal processing, a significant cost in terms of chip area and power consumption is due to these background memory units. The multidimensional signals are usually modeled in behavioral descriptions with array variables. In the algorithmic specifications of our target applications, many of the array references cover large amounts of scalars. Therefore, the efficient handling of array references in the specifications for image and video processing is crucial for obtaining low cost memory allocation solutions. This paper addresses a central problem which arises when handling the array variables in behavioral specifications: the computation of the number of scalars covered by an array reference. This problem is closely related to the computation of dependences in data-flow analysis. The novel algorithms proposed in this paper are embedded in the ATOMIUM environment-a memory management system for multidimensional signal processing.

Memory cost is responsible for a large amount of the chip and/or board area of customized video and image processing system realizations. In this paper, we present a novel technique-founded on data-flow analysis which allows one to address the problem of background memory size evaluation for a given nonprocedural algorithm specification, operating on multidimensional signals with affine indexes. Most of the target applications are characterized by a huge number of signals, so a new polyhedral data-flow model operating on groups of scalar signals is proposed. These groups are obtained by a novel analytical partitioning technique, allowing to select a desired granularity, depending on the application complexity. The method incorporates a way to tradeoff memory size with computational and controller complexity.>

Memory cost is typically responsible for up to 80% of the chip and/or board area of most video and image processing system realizations. We present a novel technique - founded on data-flow analysis - which allows us to address the problem of background memory size evolution for a given nonprocedural algorithm specification. Usually, the number of signal instances is huge, so a new data-flow model grouping scalar signals in so-called basic sets is proposed. The method also incorporates a way to trade-off memory size with computational and controller complexity.

Multidimensional (M-D) signal processing is a key component of most real-time signal and data processing VLSI systems in industry. Handling the M-D nature of data in an efficient way is crucial to arrive at acceptable system implementations. This aspect of design has often been ignored up to now in high-level synthesis. In this paper, a polyhedral based model is presented for the linear, piecewise linear and data dependent signal indexing as occurring in practical M-D signal processing applications. The model features a mathematical description of dependencies between individual operations and signal instances of M-D signals for all algorithms that contain signal indexing specified by a mixture of indexing by iterators and M-D signals embedded in the data flow. The exact modeling of M-D signal indexing is especially essential for deriving alternative control flow structures for a given data flow specification. Exploration of various control flow structures allows one to arrive at an efficient large-scale memory organization during high level synthesis of architectures, both in terms of storage locations and access order.>