NDLI: Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing

Content Provider	IEEE Xplore Digital Library
Author	Lee, Edward Ashford Messerschmitt, David G.
Copyright Year	1968
Abstract	Large grain data flow (LGDF) programming is natural and convenient for describing digital signal processing (DSP) systems, but its runtime overhead is costly in real time or cost-sensitive applications. In some situations, designers are not willing to squander computing resources for the sake of programmer convenience. This is particularly true when the target machine is a programmable DSP chip. However, the runtime overhead inherent in most LGDF implementations is not required for most signal processing systems because such systems are mostly synchronous (in the DSP sense). Synchronous data flow (SDF) differs from traditional data flow in that the amount of data produced and consumed by a data flow node is specified a priori for each input and output. This is equivalent to specifying the relative sample rates in signal processing system. This means that the scheduling of SDF nodes need not be done at runtime, but can be done at compile time (statically), so the runtime overhead evaporates. The sample rates can all be different, which is not true of most current data-driven digital signal processing programming methodologies. Synchronous data flow is closely related to computation graphs, a special case of Petri nets. This self-contained paper develops the theory necessary to statically schedule SDF programs on single or multiple processors. A class of static (compile time) scheduling algorithms is proven valid, and specific algorithms are given for scheduling SDF systems onto single or multiple processors.
Sponsorship	IEEE Computer Society Technical Committee on Distributed Process IEEE Computer Society Technical Committee on VLSI IEEE Technical Committee on Computer Architecture IEEE Computer Society
Starting Page	24
Ending Page	35
Page Count	12
File Size	2942744
File Format	PDF
ISSN	00189340
Volume Number	C-36
Issue Number	1
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1987-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Signal processing Topology Schedules Programming Processor scheduling Digital signal processing Runtime synchronous data flow Block diagram computation graphs data flow digital signal processing hard real-time systems multiprocessing Petri nets static scheduling
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Software Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Pipeline interleaved programmable DSP's: Synchronous data flow programming

Cyclo-static data flow

Synchronous data flow

Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing (1987)

Rate-optimal static scheduling for DSP data flow graphs onto multiprocessors

Retiming for Synchronous Data Flow Graphs

Hierarchical scheduling of DSP programs onto multiprocessors for maximum throughput

Parallel task scheduling for the block data flow architecture

Scheduling of DSP data flow graphs with processing times characterized by fuzzy sets

Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing

Similar Documents

Pipeline interleaved programmable DSP's: Synchronous data flow programming

Cyclo-static data flow

Synchronous data flow

Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing (1987)

Rate-optimal static scheduling for DSP data flow graphs onto multiprocessors

Retiming for Synchronous Data Flow Graphs

Hierarchical scheduling of DSP programs onto multiprocessors for maximum throughput

Parallel task scheduling for the block data flow architecture

Scheduling of DSP data flow graphs with processing times characterized by fuzzy sets

Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing