In this paper considered is the problem of scheduling a large number of parallel tasks (tasks having the same release and due times) on parallel processors. It is assumed that tasks all require one unit processing time, and the release and due times are non-negative integers. Task sets each of which consists of parallel tasks are dealt with instead of individual tasks in the conventional manner. The minimum number of processors required to process the given task sets is obtained by increasing stepwise the number of processors. To this end the minimal subset of task sets which cannot be allocated to a certain fixed number of processors is determined by a linear-order breadth-first search using the result of task assignment in two different ways, one top-down and the other bottom-up. The time complexity of the overall procedure is O(min(n, m)(mn log n)) and the space complexity is O(nm), where n and m are the numbers of task sets and time slots respectively.

In this paper presented is a theorem: a planar digraph which is embedded in a plane and which has a single source and a single sink both lying on the outer face of the digraph, is acyclic, if and only if all the inner faces are acyclic. Hence the number of tiesets necessary and sufficient for guaranteeing the acyclicity of the digraph is equal to the nullity of the digraph.

In contrast to previous algorithms for reconfiguring processor arrays under the assumption that spare rows and columns are placed on the perimeter of the array or on fixed positions, our new algorithm employs movable and partitionable spare rows and columns. The objective of moving and partitioning spare rows and/or columns is the elimination of faulty processors each of which is blocked in all directions to spare processors. The results of our computer simulation indicate that reconfigurability can significantly be improved.