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/PalemSimons.sml
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 695 - (view) (download)

1 : leunga 695 (*
2 :     * This is Krishna Palem's and Barbara Simons' algorithm.
3 :     *
4 :     * -- Allen
5 :     *)
6 :     structure PalemSimons :> PALEM_SIMONS =
7 :     struct
8 :     structure G = Graph
9 :     structure A = Array
10 :    
11 :     fun rank{dag,l,d,m} =
12 :     let val G.GRAPH G = dag
13 :     val N = #capacity G ()
14 :     val d' = A.array(N,0) (* modified deadlines *)
15 :     val order = A.array(N,0) (* node id -> rank order in swr *)
16 :     val rank = A.array(N,0) (* rank order -> rank in swr *)
17 :     val tree = A.array(N,0) (* rank order -> tree *)
18 :     val content = A.array(N,0) (* rank order -> filled slots *)
19 :     val capacity = A.array(N,0) (* rank order -> max slots *)
20 :    
21 :    
22 :     fun backSchedule i =
23 :     let (* p is the current rank order within succs *)
24 :     fun initTrees([],_,_) = ()
25 :     | initTrees((j,_,d_j)::succs,last_d_j,p) =
26 :     if last_d_j = d_j then
27 :     (A.update(order,j,p);
28 :     initTrees(succs,last_d_j,p))
29 :     else
30 :     let val p = p+1
31 :     in A.update(tree,p,p); (* new tree *)
32 :     A.update(rank,p,d_j);
33 :     A.update(content,p,0);
34 :     A.update(capacity,p,(d_j - last_d_j)*m);
35 :     A.update(order,j,p);
36 :     initTrees(succs,d_j,p)
37 :     end
38 :    
39 :     fun FIND p =
40 :     let val q = A.sub(tree,p)
41 :     in if q = p then p else
42 :     let val r = FIND q
43 :     in A.update(tree,p,r); r end
44 :     end
45 :    
46 :     fun UNION(p,q) = A.update(tree,p,q)
47 :    
48 :     fun insert([],d_i) = d_i
49 :     | insert((j,l_j,d_j)::swr,d_i) =
50 :     let val ord = A.sub(order,j)
51 :     val p = FIND ord
52 :     val c = A.sub(content,p)
53 :     val _ = A.update(content,p,c + 1)
54 :     val D' = A.sub(rank,p) - c div m
55 :     val d_i = Int.min(D' - 1 - l_j,d_i)
56 :     in if c >= A.sub(capacity,p) then
57 :     let val q = FIND(A.sub(order,A.sub(tree,p-1)))
58 :     in UNION(p,q)
59 :     end
60 :     else ();
61 :     insert(swr,d_i)
62 :     end
63 :    
64 :     val succs = #out_edges G i
65 :     val list = map (fn e as (_,j,_) => (j,l e,A.sub(d',j))) succs
66 :     fun byRank((_,_,d_i),(_,_,d_j)) = d_i > d_j
67 :     val _ = initTrees(ListMergeSort.sort byRank list,~123456789,~1)
68 :     fun byLatencyAndRank((_,l_i,d_i),(_,l_j,d_j)) =
69 :     l_i < l_j orelse (l_i = l_j andalso d_i < d_j)
70 :     val d_i = insert(ListMergeSort.sort byLatencyAndRank list,
71 :     d(i,#node_info G i))
72 :     in A.update(d',i,d_i)
73 :     end
74 :    
75 :     in (* backward scheduling in reverse topological order *)
76 :     app backSchedule
77 :     (GraphTopsort.topsort (ReversedGraphView.rev_view dag)
78 :     (map #1 (#nodes G ())));
79 :     {d'=d'}
80 :     end
81 :    
82 :     end

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