Memory Architecture Exploration for Programmable Embedded Systems

by Grun, Peter; Dutt, Nikil; Nicolau, Alexandru

• ISBN13: 9781402073243
• ISBN10: 1402073240
• Format: Hardcover
• Copyright: 2003-01-01
• Publisher: Springer Verlag

Summary

Continuing advances in chip technology, such as the ability to place more transistors on the same die (together with increased operating speeds) have opened new opportunities in embedded applications, breaking new ground in the domains of communication, multimedia, networking and entertainment. New consumer products, together with increased time-to-market pressures have created the need for rapid exploration tools to evaluate candidate architectures for System-on-Chip (SoC) solutions. Such tools will facilitate the introduction of new products customized for the market and reduce the time-to-market for such products. While the cost of embedded systems was traditionally dominated by the circuit production costs, the burden has continuously shifted towards the design process, requiring a better design process, and faster turn-around time. In the context of programmable embedded systems, designers critically need the ability to explore rapidly the mapping of target applications to the complete system. Moreover, in today's embedded applications, memory represents a major bottleneck in terms of power, performance, and cost. In particular, Memory Architecture Exploration for Programmable Embedded Systems addresses efficient exploration of alternative memory architectures, assisted by a "compiler-in-the-loop" that allows effective matching of the target application to the processor-memory architecture. This new approach for memory architecture exploration replaces the traditional black-box view of the memory system and allows for aggressive co-optimization of the programmable processor together with a customized memory system. The book concludes with a set of experiments demonstrating the utility of this exploration approach. The authors perform architecture and compiler exploration for a set of large, real-life benchmarks, uncovering promising memory configurations from different perspectives, such as cost, performance and power. Moreover, the authors compare the Design Space Exploration heuristic with a brute force full simulation of the design space, to verify that the heuristic successfully follows a true pareto-like curve. Such an early exploration methodology can be used directly by design architects to quickly evaluate different design alternatives, and make confident design decisions based on quantitative figures. Memory Architecture Exploration for Programmable Embedded Systems is designed for different groups in the embedded systems-on-chip arena. First, the book is designed for researchers and graduate students interested in memory architecture exploration in the context of compiler-in-the-loop exploration for programmable embedded systems-on-chip. Second, the book is intended for embedded system designers who are interested in an early exploration methodology, where they can rapidly evaluate different design alternatives, and customize the architecture using system-level IP blocks, such as processor cores and memories. Third, the book can be used by CAD developers who wish to migrate from a hardware synthesis target to embedded systems containing processor cores and significant software components. CAD tool developers will be able to review basic concepts in memory architectures with relation to automatic compiler/simulator software toolkit retargeting. Finally, since the book presents a methodology for exploring and optimizing the memory configuration for embedded systems, it is intended for managers and system designers who may be interested in the emerging embedded system design methodologies for memory-intensive applications.

Table of Contents

List of Figures	ix
List of Tables	xiii
Preface	xv
Acknowledgments	xv
Introduction	1	(8)
Motivation	1	(1)
Memory Architecture Exploration for Embedded Systems	2	(5)
Book Organization	7	(2)
Related Work	9	(8)
High-Level Synthesis	9	(1)
Cache Optimizations	10	(1)
Computer Architecture	11	(1)
Disk File Systems	12	(1)
Heterogeneous Memory Architectures	13	(3)
Network Processors	14	(1)
Other Memory Architecture Examples	15	(1)
Summary	16	(1)
Early Memory Size Estimation	17	(14)
Motivation	17	(1)
Memory Estimation Problem	18	(2)
Memory Size Estimation Algorithm	20	(5)
Data-dependence analysis	22	(1)
Computing the memory size between loop nests	23	(1)
Determining the bounding rectangles	23	(1)
Determining the memory size range	24	(1)
Improving the estimation accuracy	25	(1)
Discussion on Parallelism vs. Memory Size	25	(2)
Experiments	27	(1)
Related Work	28	(1)
Summary	29	(2)
Early Memory and Connectivity Architecture Exploration	31	(48)
Motivation	31	(1)
Access Pattern Based Memory Architecture Exploration	32	(14)
Our approach	32	(2)
Illustrative example	34	(3)
The Access Pattern based Memory Exploration (APEX) Approach	37	(1)
Access Pattern Clustering	37	(2)
Exploring Custom Memory Configurations	39	(1)
Experiments	39	(1)
Experimental Setup	40	(1)
Results	41	(4)
Related Work	45	(1)
Connectivity Architecture Exploration	46	(28)
Our approach	47	(1)
Illustrative example	48	(3)
Connectivity Exploration Algorithm	51	(4)
Cost, performance, and power models	55	(2)
Coupled Memory/Connectivity Exploration strategy	57	(2)
Experiments	59	(1)
Experimental Setup	59	(1)
Results	60	(12)
Related Work	72	(2)
Discussion on Memory Architecture	74	(1)
Summary and Status	75	(4)
Memory-Aware Compilation	79	(30)
Motivation	79	(1)
Memory Timing Extraction for Efficient Access Modes	80	(14)
Motivating Example	81	(2)
Our Approach	83	(1)
Timgen: Timing extraction algorithm	84	(5)
Experiments	89	(1)
Experimental Setup	89	(1)
Results	90	(2)
Related Work	92	(2)
Memory Miss Traffic Management	94	(13)
Illustrative example	95	(3)
Miss Traffic Optimization Algorithm	98	(3)
Experiments	101	(1)
Experimental setup	102	(1)
Results	102	(3)
Related Work	105	(2)
Summary	107	(2)
Experiments	109	(10)
Experimental setup	109	(1)
Results	110	(7)
The Compress Data Compression Application	110	(4)
The Li Lisp Interpreter Application	114	(2)
The Vocoder Voice Coding Application	116	(1)
Summary of Experiments	117	(2)
Conclusions	119	(2)
Summary of Contributions	119	(1)
Future Directions	120	(1)
References	121	(6)
Index	127