Job Scheduling in a Multi-layer Vision System
We consider job scheduling in a multi-layer vision system. We model this problem as scheduling a number of jobs, which are made of multiprocessor tasks, with arbitrary processing times and arbitrary processor requirements in a two-layer system. Our object
- PDF / 126,946 Bytes
- 5 Pages / 431 x 666 pts Page_size
- 89 Downloads / 215 Views
Abstract. We consider job scheduling in a multi-layer vision system. We model this problem as scheduling a number of jobs, which are made of multiprocessor tasks, with arbitrary processing times and arbitrary processor requirements in a two-layer system. Our objective is to minimize the makespan. We have developed several heuristic algorithms that include simple sequencing and scheduling rules. The computational experiments show that three of these heuristic algorithms are efficient.
1
Introduction
A multi-layer vision system provides both spatial and temporal parallelism for solving integrated vision problems [1, 6]. However, its performance does not only depend on the performance of its components but also efficient utilization of them, which can be achieved by effective handling of data partitioning, task mapping, and job scheduling. Although data partitioning and task mapping are well studied in the literature, the job scheduling aspect is usually ignored [3]. In this paper, job scheduling on a multi-layer computer vision architecture is considered. In this architecture, a typical integrated vision algorithm employs more than one feature extracting algorithm to strengthen the evidence about object instances. This requires multiple low and intermediate level algorithm pairs to be performed on a single image frame. More specifically, every incoming image frame first initiates a number of algorithms at the first layer, and then the output of these algorithms for that image is passed on to the second layer where another set of algorithms is initiated, and so on. Due to data dependency between low, intermediate, and high level algorithms, parallelism is exploited by executing them at the dedicated layers of a multi-layer system creating a pipelining effect for continuous image frames. On the other hand, spatial parallelism is exploited by decomposing an operation to the processors of a layer. We can model the above problem as follows: There is a set J of n independent and simultaneously available jobs (algorithm pairs) to be processed in a two-stage flow-shop where stage j has mj identical parallel processors (j = 1, 2). Each job Ji ∈ J has two multiprocessor tasks (MPTs), namely (i, 1) and (i, 2). P. Amestoy et al. (Eds.): Euro-Par’99, LNCS 1685, pp. 317–321, 1999. c Springer-Verlag Berlin Heidelberg 1999
318
M. Fikret Ercan, Ceyda O˘ guz, and Yu-Fai Fung
M P T (i, j) should be processed on sizeij processors (processor requirement) simultaneously at stage j for a period of pij (processing time) without interruption (i = 1, 2, . . . , n and j = 1, 2). Jobs flow through from stage 1 to stage 2 by utilizing any of the processors while satisfying the flow-shop and the MPT constraints. The objective is to find an optimal schedule for the jobs so as to minimize the maximum completion time of all jobs, i.e. the makespan, Cmax . In this scheduling problem both the processing times and the processor requirements are assumed to be known in advance. Although these parameters for some vision algorithms cannot be known u
Data Loading...