Wu Hui
Email Address
wuh@comp.nus.edu.sg
4 results
Publication Search Results
Now showing 1 - 4 of 4
Publication Fast algorithm for scheduling instructions with deadline constraints on RISC machines(2000) Wu, Hui; Jaffar, Joxan; Yap, Roland; COMPUTER SCIENCEWe present a fast algorithm for scheduling UET(Unit Execution Time) instructions with deadline constraints in a basic block on RISC machines with multiple processors. Unlike Palem and Simon's algorithm, our algorithm allows latency of lij = -1 which denotes that instruction vj cannot be started before vi. The time complexity of our algorithms is O(ne + nd), where n is the number of instructions, e is the number of edges in the precedence graph and d is the maximum latency. Our algorithm is guaranteed to compute a feasible schedule whenever one exists in the following special cases: 1) Arbitrary precedence constraints, latencies in {0, 1} and one processor. In this special case, our algorithm improves the existing fastest algorithm from O(ne + e′ log n) to O(min{ne, n2.376}), where e′ is the number of edges in the transitively closed precedence graph. 2) Arbitrary precedence constraints, latencies in {-1, 0} and two processors. In the special case where all latencies are 0, our algorithm degenerates to Garey and Johnson's two processor algorithm. 3) Special precedence constraints in the form of monotone interval graph, arbitrary latencies in {-1, 0, 1, ..., d} and multiple processors. 4) Special precedence constraints in the form of in-forest, equal latencies and multiple processors. In the above special cases, if no feasible schedule exists, our algorithm will compute a schedule with minimum lateness. Moreover, by setting all deadlines to a sufficiently large integer, our algorithm will compute a schedule with minimum length in all the above special cases and the special case of out-forest, equal latencies and multiple processors.Publication An efficient algorithm for scheduling instructions with deadline constraints on ILP processors(2001) Wu, H.; Jaffar, J.; COMPUTER SCIENCEWe propose an efficient algorithm for scheduling UET (Unit Execution Time) instructions with deadline constraints on ILP (Instruction Level Parallelism) processors with multiple functional units of different types. The time complexity of our algorithm is O(ne + nd), where n is the number of instructions, e is the number of edges in the precedence graph and d is the maximum latency. Our algorithm is guaranteed to compute a feasible schedule whenever one exists in the following special cases: I) Arbitrary precedence constraints, latencies in {-1, 0} and two functional units. 2) In-forest, equal latencies and multiple functional units. 3) Monotone interval graph and multiple functional units. For all above special cases, if no feasible schedule exists, our algorithm will compute a schedule with minimum lateness. In each of the above special cases, no polynomial time algorithm existed before. Moreover, by setting all deadlines to a sufficiently large integer, our algorithm will compute a schedule with minimum length in all the above special cases.Publication An efficient distributed deadlock avoidance algorithm for the AND model(2002) Wu, H.; Chin, W.-N.; Jaffar, J.; COMPUTER SCIENCEA new rank-based distributed deadlock avoidance algorithm for the AND resource request model is presented. Deadlocks are avoided by dynamically maintaining an invariant Con(WFG): For each pair of processes pi and pj, pi is allowed wait for process pj iff the rank of pj is greater than that of pi for the WFG (Wait-For Graph). Our algorithm neither restricts the order of resource requests nor needs a priori information about resource requests nor causes unnecessary abortion of processes. Multidimensional ranks, which are partially ordered and dynamically modified, are used to drastically reduce the cost of maintaining Con(WFG). Our simulation results show that the performance of our algorithm is better than that of existing algorithms.Publication Two processor scheduling with real release times and deadlines(2002) Wu, H.; Jaffar, J.; COMPUTER SCIENCEIn a hard real-time system, critical tasks are subject to timing constraints such as release times and deadlines. All timing constraints must be satisfied when tasks are executed. Nevertheless, given a set of tasks, finding a feasible schedule which satisfies all timing constraints is NP-complete even on one processor. In this paper, we study the following special non-preemptive two processor scheduling problem: Given a set of UET (Unit Execution Time) tasks with arbitrary precedence constraints, individual real release times and deadlines, find a feasible schedule on two identical processors whenever one exists. The complexity status of this problem has been open for a long time, we propose the first polynomial algorithm for this problem. Our algorithm is underpinned by the key consistency notion: Successor-tree-consistency. The time complexity of our algorithm is O(n4), where n is the number of tasks.