The problem of multiprocessor scheduling is to find out an efficient way to assign tasks of programs to the given processors in order to minimize the total execution time for the programs. To use the limited processors to efficiently execute programs, it is important to find out an optimal scheduling method. There is a multiprocessor system, called data-flow computer, which takes notice of data flows of the programs and whose programs are represented by program net. Generally a program net consists of three types of nodes: AND-node, OR-node and SWITCH-node, which respectively represent arithmetic/logical, data merge and context switch operations. In this paper, we discuss on optimal two-processor scheduling for the acyclic SWITCH-less program nets, whose AND-nodes are allowed to possess two input edges. At first, we propose a new priority list, and then give the properties of the priority list. Finally, we do the scheduling for a program net by the proposed priority list and farther compare the scheduling result with that generated by our previously proposed priority list in order to show the effectiveness of the new proposed priority list.
展开▼
