Joint Minimization of Code and Data for Synchronous Dataflow ProgramsObjectiveQuick OverviewMotivationSchedules and LoopsImpact of schedule on buffer sizeR-SchedulesDynamic Programming AlgorithmHeuristic SolutionDirected Acyclic SDF graphsHeuristic – Minimum legal cuts into Bounded SetsIn retrospectPossible improvements – future workJoint Minimization of Code and Data for Synchronous Dataflow ProgramsKaushik RavindranEE 249 – PresentationObjectiveDevelop a methodology for chain-structured SDF graphs to minimizeCode sizeBuffer memoryExtend this into heuristic solutions for general acyclic SDF graphsQuick OverviewDataflow networksCollection of functional actors connected over unbounded FIFO buffersSynchronous Dataflow (SDF)# of tokens produced per actor fixedDeadlock and boundedness are decidableA B C20 10 20 10MotivationCode size minimizationCode replication each time an actor appears in scheduleAmount of on-chip memory limitedSingle Appearance schedules – optimally compact inline representation of SDFBuffer memory optimizationChoose schedule that minimizes buffer memorySchedules and LoopsRevisitRepetitions vectorqG = (1, 2, 4) - Minimum number of actor firings•q[source(e)] * produce(e) = q[sink(e)]*consume(e)Flat single appearance schedule•(ω(1A)(2B)(4C))(nS1S2…Sk) – ‘n’ successive firings of S1…SkA B C20 10 20 10Impact of schedule on buffer sizeValid schedules Buffer size1. ABCBCCC 502. A(2B(2C)) 403. A(2B)(4C) 604. A(2BC)(2C) 50For a consistent SDF graph, there exists a fully reduced single appearance schedule occupying minimum possible buffer memoryA B C20 10 20 10R-SchedulesRecursively decompose chain-structured graph (G) into left (SL) and right (SR) subgraphsSet or R-schedules always contains a schedule that attains minimum buffer requirementNumber of R-schedules = (1/n)(2n-2 C n-1)where n = number of actors in chain SDFDynamic Programming AlgorithmDetermine R-schedule that minimizes buffer memory requirementMinimum buffer memory requirement is cost of subgraphs and cost of splitb[i,j] = min(b[i,k] + b[k+1,j] + ci,j[k])for i <= k < jRunning time O(n3)Heuristic SolutionIntroduce split on edge where minimum amount of data is transferredAverage run time O(n * log (n)) Can apply heuristic to arbitrary acyclic SDFPartition SDF into smaller subgraphsApply exact dynamic programming algorithm to minimum size subgraphsDirected Acyclic SDF graphsTopological sortOrdering of vertices, such that source vertex of each edge occurs earlier than sink vertexFlat single appearance schedule corresponds to any valid topological sortFour possible topological sortsABCDstHeuristic – Minimum legal cuts into Bounded SetsExtend heuristic for chain-structured graphFind cut with minimum amount of data transferred•Kernighan and Lin approachRecursively partition left and right halves to obtain schedule bodiesRun dynamic programming algorithm to optimize scheduleIn retrospectMain objectivesMinimize code size•Through single appearance schedulesMinimize buffer memory•Through buffer optimal looped schedulesDynamic programming algorithmFor well ordered SDF graphsHeuristic algorithms For general acyclic SDF graphsPossible improvements – future workConsideration of a shared buffer approachCalculate minimum shared buffer size for looped schedulesTrade-offs between code size Vs buffer sizeConsider a multiple appearance schedule that could optimize buffer usageExtend study to arbitrary SDF
View Full Document
Unlocking...