Operation Scheduling: Algorithms and Applications

Operation scheduling (OS) is an important task in the high-level synthe- sis process. An inappropriate scheduling of the operations can fail to exploit the full potential of the system. In this chapter, we try to give a comprehensive cov- erage on the heuristic algorithms currently available for solving both timing and resource constrained scheduling problems. Besides providing a broad survey on this topic, we focus

on some of the most popularly used algorithms, such as List Scheduling, Force-Directed Scheduling and Simulated Annealing, as well as the newly introduced approach based on the Ant Colony Optimization meta-heuristics. We discuss in details on their applicability and performance by comparing them on solution quality,performancestability, scalability, extensibility,and computation cost. Moreover,as an application of operation scheduling,we introduce a novel uni- formed design space exploration method that exploits the duality of the time and resource constrained scheduling problems, which automatically constructs a high quality time/area tradeoff curve in a fast, effective manner. Keywords: Design space exploration, Ant colony optimization, Instruction scheduling, MAX–MIN ant system 13.1 Introduction As fabrication technology advances and transistors become more plentiful, modern computingsystemscanachievebettersystemperformancebyincreasingthe amount ofcomputationunits.It is estimatedthatwe will be ableto integratemorethana half billion transistors on a 468mm 2 chip by the year of 2009 [38]. This yields tremen- dous potential for future computing systems, however, it imposes big challenges on how to effectively use and design such complicated systems. As computing systems become more complex, so do the applications that can run on them. Designers will increasingly rely on automated design tools in order P. Coussy and A. Morawiec (eds.) High-Level Synthesis. c©Springer Science + Business Media B.V. 2008 231 232 G. Wang et al. to map applications onto these systems. One fundamental process of these tools is mapping a behavioral application specification to the computing system. For exam- ple, the tool may take a C functionand create the code to programa microprocessor. This is viewed as software compilation. Or the tool may take a transaction level behavior and create a register transfer level (RTL) circuit description. This is called hardware or behavioral synthesis [31]. Both software and hardware synthesis flows are essential for the use and design of future computing systems. Operation scheduling (OS) is an important problem in software compilation and hardwaresynthesis. An inappropriateschedulingofthe operationscan fail to exploit the full potential of the system. Operation scheduling appears in a number of dif- ferent problems, e.g., compiler design for superscalar and VLIW microprocessors [23], distributed clustering computation architectures [4] and behavioral synthesis of ASICs and FPGAs [31]. Operationschedulingis performedona behavioraldescriptionofthe application. Thisdescriptionistypicallydecomposedintoseveralblocks(e.g.,basic blocks),and each of the blocks is represented by a data flow graph (DFG). Operation scheduling can be classified as resource constrained or timing con- strained. Given a DFG, clock cycle time, resource count and resource delays, a resource constrained scheduling finds the minimum number...

Website: cseweb.ucsd.edu | Filesize: -
No of Page(s): 25
Download Operation Scheduling: Algorithms and Applications.pdf