Shamik Bandyopadhyay

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-105

August 14, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-105.pdf

A scratchpad memory is a fast compiler-managed on-chip memory that replaces the hardware managed cache in several embedded processors. Scratchpad memories provide better real-time guarantees, and significantly lower overheads in energy consumption and area as compared to caches [9]. Several allocation schemes exist for mapping variables, data and code to the scratchpad memory. However, none of these schemes seek to optimize the allocation based on the control flow and data flow information that can be gleaned from block diagram based programs in frameworks in LabVIEW and Ptolemy II [7]. In this report we present methods for scratchpad memory allocation of block diagram programs composed under the Heterochronous Dataflow (HDF) model of computation [3]. HDF is a heterogeneous composition of Synchronous Dataflow (SDF) [1] and Finite State Machines (FSM). It is significantly more expressive than SDF since it allows rate changes in actors during execution. The memory allocation method exploits the coarse grained software architecture and semantics of the HDF models to gather information about the temporal pattern and access frequencies of memory references and the memory requirements of the computational blocks. This information is processed using an Integer Linear Program (ILP) based framework to generate the optimal memory allocation for each state in the HDF graph. We also present a modified version of the algorithm which generates multiple allocations for each state. The ILP based allocation algorithm is shown to perform significantly better than caches. We also show that the allocation algorithm increases predictability by being completely independent of the scheduling technique used to generate the execution schedule for the HDF model. The algorithmic modification that generates multiple allocations per state is shown to perform better than the original algorithm for actor code allocation for intermediate scratchpad sizes. We present a strict upper bound on the memory access time of a HDF model allocated to scratchpad using the above algorithm. We also present several interesting directions for future exploration.

Advisors: Edward A. Lee

---

BibTeX citation:

@mastersthesis{Bandyopadhyay:EECS-2006-105,
    Author= {Bandyopadhyay, Shamik},
    Title= {Automated Memory Allocation of Actor Code and Data Buffer in Heterochronous Dataflow Models to Scratchpad Memory},
    School= {EECS Department, University of California, Berkeley},
    Year= {2006},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-105.html},
    Number= {UCB/EECS-2006-105},
    Abstract= {A scratchpad memory is a fast compiler-managed on-chip memory that replaces the hardware managed cache in several embedded processors. Scratchpad memories provide better real-time guarantees, and significantly lower overheads in energy consumption and area as compared to caches [9]. Several allocation schemes exist for mapping variables, data and code to the scratchpad memory. However, none of these schemes seek to optimize the allocation based on the control flow and data flow information that can be gleaned from block diagram based programs in frameworks in LabVIEW and Ptolemy II [7]. 
	In this report we present methods for scratchpad memory allocation of block diagram programs composed under the Heterochronous Dataflow (HDF) model of computation [3]. HDF is a heterogeneous composition of Synchronous Dataflow (SDF) [1] and Finite State Machines (FSM). It is significantly more expressive than SDF since it allows rate changes in actors during execution. The memory allocation method exploits the coarse grained software architecture and semantics of the HDF models to gather information about the temporal pattern and access frequencies of memory references and the memory requirements of the computational blocks. This information is processed using an Integer Linear Program (ILP) based framework to generate the optimal memory allocation for each state in the HDF graph. We also present a modified version of the algorithm which generates multiple allocations for each state.
	The ILP based allocation algorithm is shown to perform significantly better than caches. We also show that the allocation algorithm increases predictability by being completely independent of the scheduling technique used to generate the execution schedule for the HDF model.   The algorithmic modification that generates multiple allocations per state is shown to perform better than the original algorithm for actor code allocation for intermediate scratchpad sizes. We present a strict upper bound on the memory access time of a HDF model allocated to scratchpad using the above algorithm. We also present several interesting directions for future exploration.},
}

EndNote citation:

%0 Thesis
%A Bandyopadhyay, Shamik 
%T Automated Memory Allocation of Actor Code and Data Buffer in Heterochronous Dataflow Models to Scratchpad Memory
%I EECS Department, University of California, Berkeley
%D 2006
%8 August 14
%@ UCB/EECS-2006-105
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-105.html
%F Bandyopadhyay:EECS-2006-105