Paper Authors

Abstract

NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Dataflow Scheduling and Exploring Digital System Design Alternatives Abstract

Dataflow scheduling is a powerful technique for exploring design alternatives at the system level. Efficient scheduling is, however, a complicated task. Software tools are often used in high-level synthesis to schedule a design specification. Since high-level synthesis is not yet widely accepted as a method of design entry, most students do not appreciate the significance of scheduling to the tradeoffs of system-level digital design. In this paper, we use a sorting algorithm to investigate the role of scheduling to the design of sorting networks. In class, we begin with a serial specification. Then, the as- soon-as-possible (ASAP) and the as-late-as-possible (ALAP) scheduling algorithms are applied to the original description. Students are also encouraged to define their own schedules and compare them with the serial, ASAP, and ALAP schedules. The impact of various schedules on the number of sorting elements, registers, multiplexers, and control steps are analyzed. After students have derived much insight of the problem, several scheduling algorithms available in the literature such as the force-directed scheduling are studied. To investigate the impact of dataflow scheduling on hardware implementation, the data paths and controllers of two scheduled dataflow specifications are presented. The tradeoffs between hardware cost and system performance is analyzed. The methodology was taught in an “Advanced Digital Design” course as a design space exploration skill. Students’ feedback indicated that the method was very systematic and robust, and constituted a powerful digital design technique. Given the instruction set specification of a computer, the technique is also applicable to explore the design space of a central-processing-unit (CPU). In addition, the materials give students a clear demonstration for the structures of a CPU, including the separation of data paths and controller as well as the impact of multiple functional units. With these considerations in mind, the module was also offered in the course of “High-Performance Computer Architectures” for students to understand the fundamentals of CPU design.

1. Introduction

As the complexity of digital design continues to increase, system level design is becoming the focus of digital design activities. These days digital design often begins with an algorithmic specification. The algorithmic description is then scheduled [8, 9]. The structure of a design is generated based on the scheduled data and control flow specification.

Given a scheduled dataflow specification, a clique-partitioning procedure can be applied to the synthesis of data paths in a digital system [9]. Slicing techniques can be used to produce a controller for the data paths [10]. In other words, hardware resources requirement is determined by the scheduled data flow. Indeed, dataflow scheduling has become an important technique for exploring design alternatives. In this paper, we describe how we used the design of sorting networks to teach students the new paradigm of dataflow scheduling for exploring digital system design alternatives.

• Citation

• Format
  • APA
  • APA - LaTeX bibitem
  • MLA
  • MLA - LaTeX bibitem
  • Bibtex
  • EndNote - RIS

Tseng, C. (2006, June), Dataflow Scheduling And Exploring Digital System Design Alternatives Paper presented at 2006 Annual Conference & Exposition, Chicago, Illinois. 10.18260/1-2--634