Efficient Encoding for Exact SymbolicAutomata-Based SchedulingSteve HaynalForrest BrewerDepartment of Electrical and Computer EngineeringUniversity of California, Santa Barbara, U.S.A.haynal @umbra. ece.ucsb.edu, [email protected]. edu1. MSTMCTThis paper presents an efficient encoding andautomaton construction which improves per-formance of automata-based scheduling tech-niques. The encoding preserves howledge ofwhat operationsoccurred previously butexcludes when they occurred, a~owing greatersharing among schedutig traces. The tech-nique inherits au of the features of BDD-basedcontrol dominated schedu~g including sys-tematic speculation.Without conventionalpruning, au schedties for several large samplesare quicMy constructed.1.1 KeywordsHigh-level ~nthesis, scheduling, BDD, automata2. ~TRODUCTIONme schduling problem occurs across diverse ara of applicationfrom nehvorking to manufacturing to high-level synthesis of digitalsystems (HLS). Scheduling which assigns operations to time-slotsin a synchronous system subject to data and control-flow depen-dencies as well as reource constraints is a key component of manyHLS systems. Consequently solving this problem efficiently is adirect way to enhance the abilities of such systems.hfost solutions to the scheduling problem fall into two categori= i)heuristics and ii) integer Iin= programming (ILP). Heuristicschedulers (i.e.[1][9]) find good solutions for large problemsquickly but suffm with tightly constrained problems where ~rlypruning decisions exclude mdidates lading to superior solutions.lLP schedulers (i.e.[3][4]) exactly solve scheduling but have diff-icultieswith time complexity and control constraint formulation.Heuristic and ILP scheduling methods produce a single schedule ata time. Finding this schedule, especially an optimal one, oftenbecomes incr=ingly difficult as more constraints are added to theproblem formulation. Symbolic methods, (i.e [2][6][7][8][1O])arePefission to tie di#hl or tid copies ofd or pti of ti it~orkfor pemml or&<sroom use k ~nted \titSrout fw pmtided tkt copies xe not =de or distibuted forprofit or comerdd adk.atsge nd tit copies b- tkis notice md the Wcitation on tie fit paga Tocopy othatfie, to mpubhh, to pt.on semem or tored~tibute to kts, rqti~ prior s@c -on red/or a fee.ICC~9S. Sm Jose.CA USAo 199sAChf l-5sii3&s-z9s/MI l.S5.moften effective in finding exact solutions in highly constrainedproblem formulations. Furthermore, since all solutions are enumer-ated, post-process pruning can be used to apply additional con-straints which may not have eticient formulation for generalschedula. Further, symbolic methods allow much more efficientformulation of control dependencies and environmental timingconstraints. However, with symbolic methods, the key to success isto reduce the representation size of the solution sets. Methods toaccomplish this include adding additional constraints to the probIem, pruning suboptimal candidates early in the s~rch, and eti-cient encoding techniques.An exact symbolic scheduling technique was presented in [7][S].~is method uses ROBDDS to dmcribe scheduling constraints andcompress solution sets. In this formulation, =ch operation in aCDFG (Control Data Flow Graph) is assigned a bool=rr variablefor ach time-step in the schedule. ~is variable indicates whetheror not the operation is scheduled during that time-step. Constraints,derivd from the CDFG and environment are added to the con-struction. Guard variablm are employed to distinguish controlpaths. Although this technique performed well, complexity probIems arose for lengthy schedules. Worse, since every exact historyfor all viable traces is kepg the encoding eficiency declines forschedules with many complex alternative histories.Symbolic ROBDD automata-based schedulers were described in[2][6][1O]. In [6], an exact operand scheduling technique is pre-sented for predefine datapaths. ~is technique allows opemnds tobe lost and later produced again in order to find optimal schedulesmeeting tight memory constraints. In [2][10], system timing andsynchronization requirements are encapsulated in finite-statemachine (FSM) descriptions. All constraints are formulated asautomaton and product machines are built and traversed. ~is prod-uct machine becomes prohibitively large for practical sized probIems. Furthermore, causality (as checked for by causal validation inSection 4.2) is not confirmed.In this paper we present an exact symbolic automata-based sched-uler. Our immediate innovation is an efficient encoding and autom-aton construction which improves performance of exact symbolicscheduling techniques. Fundamentally, this technique groupstogether schedules with common although not necessarily identicalhistoria when exploring the schedule solution space. ~is isaccomplished using an encoding which only preserves whether ornot an operation has been scheduled but not precisely when. In thisway, we minimize the problems of [7] for long schedules and of[2][1O]with regards to automata size.Wepursue an automata-based representation since it provides clearpotential [2][1O] for describing control and protocol-intensivecycle-varying systems. ~is ability is a key part of our long-termHLS goal. Fufiher, we utilize exact symbolic ROBDD techniquesbecause of their demonstrated success in finding all optimal con-477_... . . .-strained solutions [7][S]. JVe wish to apply these techniqu= toconstrairrd critical portions of large scaIe system designs. Suchsystems are fiiled with complex subsystem interactions lvhichmay be amenable to Bool=n automata representation.3. CDFG BOOLEAN FOWULATION\Vedefine a CDFG as a directed graph where nodti denote opera-tions, forks orjoins and arcs represent dependencies. Fig. 1showsa simple CDFG. In this example, the directed arcs from operation1to the fork andjoin denotes a control dependency. Consequently,the resolution of the fork and join remains unknown until afteroperation 1 has been scheduled. It is important to note that opera-tions 3 and 4 can be speculatively executed before the fork isresolved. In this everr6 operations 3 and 4 must both be scheduledregardless of the control resolution. The right-hand side of Fig. 1shows this speculative tmnsfomation. Finally, the directed archorn operation 1 to operation 2 represents a data dependency.Hence operation 2 can only be scheduled afier operation 1.Figure 1. Simple CDFG before and after speculation.In our formulation, data and control constraints are extracted froma user