مرکز منطقه ای اطلاع رساني علوم و فناوري

DocumentCode :

3167758

Title :

Linear scheduling is close to optimality

Author :

Darte, Alain ; Khachiyan, Leonid ; Robert, Yves

fYear :

1992

fDate :

4-7 Aug 1992

Firstpage :

Lastpage :

Abstract :

This paper deals with the problem of finding optimal schedulings for uniform dependence algorithms. Given a convex domain, let T _f be the total time needed to execute all computations using the free (greedy) schedule and let T_l be the total time needed to execute all computations using the optimal linear schedule. The authors´ main result is to bound T_l/ T_f and T_l-T_f for sufficiently `fat´ domains

Keywords :

parallel algorithms; scheduling; convex domain; linear scheduling; optimal schedulings; optimality; uniform dependence algorithms; Algorithm design and analysis; Computer science; Design optimization; Optimal scheduling; Optimizing compilers; Processor scheduling; Scheduling algorithm; Sufficient conditions; Systolic arrays; Terminology;

fLanguage :

English

Publisher :

ieee

Conference_Titel :

Application Specific Array Processors, 1992. Proceedings of the International Conference on

Conference_Location :

Berkeley, CA

ISSN :

1063-6862

Print_ISBN :

0-8186-2967-3

Type :

conf

DOI :

10.1109/ASAP.1992.218583

Filename :

218583

Link To Document :

https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=3167758