Title :
Scheduling of low level computer vision algorithms on networks of heterogeneous machines
Author :
Nolan, Adam R. ; Everding, Bryan ; Wee, William
Author_Institution :
Artificial Intell. & Comput. Vision Lab., Cincinnati Univ., OH, USA
Abstract :
Defining an optimal schedule for arbitrary algorithms on a network of heterogeneous machines is an NP complete problem. By focusing on data parallel deterministic neighborhood computer vision algorithms, a minimum time schedule can be defined in polynomial time. The scheduling model allows for any speed machine to participate in the concurrent computation but makes the assumption of a master/slave control mechanism using a linear communication network. Several vision algorithms are presented which adhere to the scheduling model. The theoretical speedup of these algorithms is discussed and empirical data is presented and compared to theoretical results
Keywords :
computational complexity; computer vision; deterministic algorithms; parallel algorithms; scheduling; NP complete problem; arbitrary algorithms; concurrent computation; data parallel deterministic neighborhood computer vision algorithms; empirical data; heterogeneous machine networks; linear communication network; low level computer vision algorithm scheduling; master/slave control mechanism; minimum time schedule; optimal schedule; scheduling model; theoretical speedup; vision algorithms; Communication networks; Communication system control; Computer networks; Computer vision; Concurrent computing; Master-slave; Optimal scheduling; Polynomials; Processor scheduling; Scheduling algorithm;
Conference_Titel :
Computer Architectures for Machine Perception, 1995. Proceedings. CAMP '95
Conference_Location :
Como
Print_ISBN :
0-8186-7134-3
DOI :
10.1109/CAMP.1995.521059