Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/scheduling/LeungPalemPnueli.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/scheduling/LeungPalemPnueli.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 695 - (view) (download)

1 : leunga 695 (*
2 :     * This is my algorithm from PACT '98.
3 :     *
4 :     * -- Allen
5 :     *)
6 :     structure LeungPalemPnueli :> LEUNG_PALEM_PNUELI =
7 :     struct
8 :    
9 :     structure G = Graph
10 :     structure A = Array
11 :     structure PQ = PriorityQueue
12 :    
13 :     exception Infeasible
14 :    
15 :     fun rank{dag,l,r,d,m} =
16 :     let val G.GRAPH G = dag
17 :     val N = #capacity G ()
18 :     val r' = A.array(N,0) (* modified release times *)
19 :     val d' = A.array(N,0) (* modified deadlines *)
20 :     val r_hat = A.array(N,0) (* backschedule modified release times *)
21 :     val d_hat = A.array(N,0) (* backschedule modified deadlines *)
22 :    
23 :     val node_ids = map #1 (#nodes G ())
24 :    
25 :     fun initReleaseTimes() =
26 :     let fun update i =
27 :     A.update(r',i,
28 :     foldr (fn (e as (j,_,_),r_i) =>
29 :     Int.max(A.sub(r',j) + l e + 1,r_i))
30 :     (r(i,#node_info G i)) (#in_edges G i))
31 :     in app update (GraphTopsort.topsort dag node_ids) end
32 :    
33 :     fun initDeadlines() =
34 :     let fun update i =
35 :     A.update(d',i,
36 :     foldr (fn (e as (_,j,_),d_i) =>
37 :     Int.min(A.sub(d',j) - l e - 1,d_i))
38 :     (d (i,#node_info G i)) (#out_edges G i))
39 :     in app update (GraphTopsort.topsort (ReversedGraphView.rev_view dag)
40 :     node_ids)
41 :     end
42 :    
43 :    
44 :     (* unit time tasks, no-precedence constraints with
45 :     * deadlines d_hat and release times r_hat.
46 :     * I'm using an asymtotically slower (n log n)
47 :     * algorithm than the one described in the paper.
48 :     *)
49 :     fun UET(S) =
50 :     let fun byReleaseTimes(i,j) = A.sub(r_hat,i) > A.sub(r_hat,j)
51 :     fun byDeadlines(i,j) = A.sub(d_hat,i) < A.sub(d_hat,j)
52 :     val ready = PQ.create byDeadlines
53 :     val ins = PQ.insert ready
54 :     fun listSchedule(waiting,t,0) = listSchedule(waiting,t+1,m)
55 :     | listSchedule(waiting,t,m) =
56 :     let val j = PQ.deleteMin ready
57 :     in t < A.sub(d_hat,j) andalso (* check for infeasbility! *)
58 :     listSchedule(waiting,t,m-1)
59 :     end handle PQ.EmptyPriorityQueue =>
60 :     (* no more ready nodes *)
61 :     let fun release(t,[]) = (t,[])
62 :     | release(t,l as j::waiting) =
63 :     if A.sub(r_hat,j) > t then (t,l)
64 :     else (ins j; release(t,waiting))
65 :     in case waiting of
66 :     [] => true (* feasible *)
67 :     | waiting as j::_ =>
68 :     let val (t,waiting) = release(A.sub(r_hat,j),waiting)
69 :     in listSchedule(waiting,t,m) end
70 :     end
71 :     in listSchedule(ListMergeSort.sort byReleaseTimes S,0,m) end
72 :    
73 :     fun backSchedule(i,r'_i,S) =
74 :     let fun loop d'_i =
75 :     if r'_i >= d'_i then raise Infeasible
76 :     else
77 :     let val _ = A.update(d_hat,i,d'_i)
78 :     val _ = A.update(r_hat,i,d'_i-1)
79 :     val _ = app (fn e as (_,j,_) =>
80 :     A.update(r_hat,j,Int.max(d'_i + l e,A.sub(r',j))))
81 :     (#out_edges G i)
82 :     in if UET S then d'_i
83 :     else loop(d'_i-1)
84 :     end
85 :    
86 :     in app (fn j => (A.update(d_hat,j,A.sub(d',j));
87 :     A.update(r_hat,j,A.sub(r',j)))) S;
88 :     loop(A.sub(d',i))
89 :     end
90 :    
91 :     fun mainLoop([],_) = ()
92 :     | mainLoop(i::U,S) =
93 :     let val r'_i = A.sub(r',i)
94 :     val S = i::S
95 :     val d'_i = backSchedule(i,r'_i,S)
96 :     in A.update(d',i,d'_i);
97 :     if d'_i <= r'_i then raise Infeasible
98 :     else mainLoop(U,S)
99 :     end
100 :     fun byNonIncreasingReleaseTimes(i,j) = A.sub(r',i) < A.sub(r',j)
101 :    
102 :     in (* initialize the modified deadlines/release times *)
103 :     initReleaseTimes();
104 :     initDeadlines();
105 :     mainLoop(ListMergeSort.sort byNonIncreasingReleaseTimes node_ids,[]);
106 :     {r'=r',d'=d'}
107 :     end
108 :    
109 :     end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0