Heterogeneous Memory Organizations in Embedded Systems: Placement of Dynamic Data Objects

Preface
Contents
Acronyms
1 Introduction
	1.1 The Memory Wall
		1.1.1 Cache Memories and Explicitly Managed Scratchpads for High-Locality and Static Data
		1.1.2 The Challenge of Dynamic Data Objects
	1.2 The Power Wall
		1.2.1 The Advent of Energy-Efficient Computing
	1.3 Energy Consumption in the Memory Subsystem
	1.4 Problem Statement and Proposal
		1.4.1 Methodology Outline
		1.4.2 Methodology Steps
	1.5 Text Organization
	References
2 Related Work
	2.1 Code Transformations to Improve Access Locality
	2.2 SW-Controlled Data Layout and Static Data Placement
	2.3 Dynamic Memory Management
	2.4 Dynamic Data Types Optimization
	2.5 Dynamic Data Placement
	2.6 Computational Complexity
	References
3 A Gentle Introduction to Dynamic Memory, Linked Data Structures and Their Impact on Access Locality
	3.1 Use Cases for Dynamic Memory
		3.1.1 Allocation of Vectors Whose Size Is Known Only at Run-Time
		3.1.2 Creation of a Collection of Data Objects with an Unknown Cardinality
		3.1.3 Construction of Dynamic Data Types (DDTs)
	3.2 Impact of Linked Data Structures on Locality
		3.2.1 Example: A Simple Case with the List DDT
		3.2.2 A More Complex Example with AVL Trees
		3.2.3 Another AVL Example, with Random Data
	3.3 Summary: DDTs Can Reduce Access Locality
	References
4 Methodology for the Placement of Dynamic Data Objects
	4.1 Choices in Data Placement
		4.1.1 The Musts of Data Placement
		4.1.2 Types of Data Placement
			4.1.2.1 Placement Policy
			4.1.2.2 Data Nature
		4.1.3 Granularity of Data Placement
			4.1.3.1 All DDTs Together
			4.1.3.2 One Pool Per DDT
			4.1.3.3 Per Individual Instance
			4.1.3.4 By Groups of DDTs
	4.2 Data Placement from a Theoretical Perspective
		4.2.1 Notes on Computational Complexity
		4.2.2 Data Placement
	4.3 A Practical Proposal: Grouping and Mapping
	4.4 Designing a Dynamic Memory Manager for Data Placement with DDT Grouping
		4.4.1 Placement According to Memory Resources
		4.4.2 Available Information
		4.4.3 Manager Structure
		4.4.4 Order of Choice
	4.5 Putting Everything Together: Summary of the Methodology
	4.6 Instrumentation and Profiling
		4.6.1 Template-Based Extraction of Allocation Information
		4.6.2 Virtual Memory Support for Data Access Profiling
			4.6.2.1 Mechanism
			4.6.2.2 Implementation
			4.6.2.3 Performance Optimization
		4.6.3 Summary
	4.7 Analysis
	4.8 Group Creation
		4.8.1 Liveness and Exploitation Ratio
		4.8.2 Algorithm Parameters
		4.8.3 Algorithm
			4.8.3.1 Justification
	4.9 Definition of Pool Structure and Algorithms
	4.10 Mapping into Memory Resources
		4.10.1 Algorithm Parameters
		4.10.2 Algorithm
		4.10.3 Platform Description
	4.11 Deployment
	References
5 Design of a Simulator for Heterogeneous Memory Organizations
	5.1 Overview
		5.1.1 Elements in the Memory Hierarchy
		5.1.2 DMM and Memory Address Translation During Simulation
		5.1.3 Life Cycle of a Memory Access in the Simulator
	5.2 Simulation of Software-Controlled Scratchpads (SRAMs)
	5.3 Simulation of Cache Memories
		5.3.1 Overlapped Accesses
		5.3.2 Direct-Mapped Caches
		5.3.3 Associative Caches
	5.4 Overview of Dynamic Memories (DRAMs)
		5.4.1 Why a DRAM Simulator
		5.4.2 DRAM Basics
	5.5 Simulation of Mobile SDRAMs
		5.5.1 Memory Working Parameters
		5.5.2 Calculations
			5.5.2.1 IDD0: Maximum Operating Current
			5.5.2.2 Shortcuts
			5.5.2.3 Power to Drive Module Pins
			5.5.2.4 Background Power
		5.5.3 Simulation
			5.5.3.1 From the IDLE State
			5.5.3.2 From the READ State
			5.5.3.3 From the WRITE State
	5.6 Simulation of LPDDR2-SDRAMs
		5.6.1 Row Activations
		5.6.2 Memory Reads
		5.6.3 Memory Writes
		5.6.4 Write Data Mask
		5.6.5 Address Organization
		5.6.6 DRAM Refreshing
		5.6.7 Memory Working Parameters
		5.6.8 Calculations
			5.6.8.1 Shortcuts
			5.6.8.2 Power of Driving Module Pins
			5.6.8.3 Background Power
		5.6.9 Simulation
			5.6.9.1 From the IDLE State
			5.6.9.2 From the READ State
			5.6.9.3 From the WRITE State
		5.6.10 A Final Consideration
	References
6 Experiments on Data Placement: Results and Discussion
	6.1 Methodology Implementation in the DynAsT Tool
		6.1.1 Parameters Used in the Experiments
	6.2 Description of the Memory Hierarchies
	6.3 Case Study 1: Wireless Sensors Network
		6.3.1 Profiling
		6.3.2 Analysis
		6.3.3 Grouping
		6.3.4 Pool Formation
		6.3.5 Mapping
		6.3.6 Simulation
	6.4 Case Study 2: Network Routing
		6.4.1 Description of the Application
		6.4.2 Experimental Results
	6.5 Case Study 3: Synthetic Benchmark—Dictionary
	6.6 Additional Discussion
		6.6.1 Suitability and Current Limitations
		6.6.2 Use Cases for the Methodology
			6.6.2.1 Application Optimization for a Fixed Platform
			6.6.2.2 Hardware Platform Exploration and Evaluation
		6.6.3 Simulation Versus Actual Execution
		6.6.4 Reducing Static to Dynamic Data Placement—or Vice Versa
		6.6.5 Order Between Mapping and Pool Formation
	References
7 Closing Remarks and Open Questions
	7.1 Summary of Main Ideas
	7.2 Open Questions
		7.2.1 Methodology and Algorithms
			7.2.1.1 Profiling
			7.2.1.2 Grouping
			7.2.1.3 Mapping
			7.2.1.4 Integration in a Complete Dynamic Memory Management Framework
			7.2.1.5 Deployment
			7.2.1.6 Simulation
			7.2.1.7 Other Areas
	7.3 Applicability to Other Environments
		7.3.1 Scale-Up Systems
		7.3.2 Scale-Out Systems
		7.3.3 New Memory Technologies
			7.3.3.1 Non-volatile Memories and the Fusion of Primary and Secondary Storage
		7.3.4 Near-Threshold Computation and Inexact Computing
	References
A Example Run of DynAsT
	A.1 Example Application
		A.1.1 Source Code and Instrumentation
		A.1.2 Instrumentation Output After Execution
	A.2 Processing with DynAsT
		A.2.1 Analysis
		A.2.2 Grouping
		A.2.3 Mapping
		A.2.4 Simulation
			A.2.4.1 Simulation for Platform with SRAM and Mobile SDRAM
			A.2.4.2 Simulation for Platform with SRAM and LPDDR2 SDRAM
			A.2.4.3 Simulation for Platform with Cache and Mobile SDRAM
Index