Citation
Shamik Bandyopadhyay. "Automated Memory Allocation of Actor Code and Data Buffer in Heterochronous Dataflow Models to Scratchpad Memory". Master's thesis, University of California, Berkeley, August, 2006.

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.

Electronic downloads

• http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-105.html

• HTML

  Shamik Bandyopadhyay. <a
  href="http://chess.eecs.berkeley.edu/pubs/331.html"
  ><i>Automated Memory Allocation of Actor Code and
  Data Buffer in Heterochronous Dataflow Models to Scratchpad
  Memory</i></a>, Master's thesis,  University of
  California, Berkeley, August, 2006.

• Plain text

  Shamik Bandyopadhyay. "Automated Memory Allocation of
  Actor Code and Data Buffer in Heterochronous Dataflow Models
  to Scratchpad Memory". Master's thesis,  University of
  California, Berkeley, August, 2006.

• BibTeX

  @mastersthesis{Bandyopadhyay06_AutomatedMemoryAllocationOfActorCodeDataBufferInHeterochronous,
      author = {Shamik Bandyopadhyay},
      title = {Automated Memory Allocation of Actor Code and Data
                Buffer in Heterochronous Dataflow Models to
                Scratchpad Memory},
      school = {University of California, Berkeley},
      month = {August},
      year = {2006},
      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.},
      URL = {http://chess.eecs.berkeley.edu/pubs/331.html}
  }
  

Posted by Christopher Brooks on 7 Jun 2007.
Groups: ptolemy
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.