Calypso: an implementation of the order graph method

Author

Cato, Gavin R. ; Reeves, Douglas S.

Author_Institution

Dept. of Comput. Sci., North Carolina State Univ., Raleigh, NC, USA

Volume

6

fYear

1996

fDate

7-10 May 1996

Firstpage

3342

Abstract

Previous efforts to speed up signal and image processing algorithms have focused on executing them in parallel on multiprocessor systems. An important issue in achieving the maximum parallelism is how to automatically partition and schedule algorithms onto the individual processors. We present the order graph method (OGM) as an effective technique for parallel task scheduling which considers interprocessor communication and network topology. Calypso is introduced as an implementation of the OGM. Results from scheduling image processing algorithms are presented. In addition, we propose some standard benchmarks that can be used to compare various methods for parallel task scheduling

Keywords

data flow graphs; distributed memory systems; image processing; network topology; parallel algorithms; processor scheduling; Calypso; distributed memory multiprocessor system; image processing algorithms; interprocessor communication; network topology; order graph method; parallel algorithms; parallel task scheduling; schedule algorithms; signal processing algorithm; standard benchmarks; Costs; Delay; Digital signal processing; Multiprocessing systems; Network topology; Parallel processing; Partitioning algorithms; Processor scheduling; Scheduling algorithm; Signal processing algorithms;

fLanguage

English

Publisher

ieee

Conference_Titel

Acoustics, Speech, and Signal Processing, 1996. ICASSP-96. Conference Proceedings., 1996 IEEE International Conference on

Conference_Location

Atlanta, GA

ISSN

1520-6149

Print_ISBN

0-7803-3192-3

Type

conf

DOI

10.1109/ICASSP.1996.550593

Filename

550593