http:// www.diachiweb.com









Hình 5

Tập Hardware (EX
h
) extremity và tập software (EX
s
) extremity
Sự thay đổi ngưỡng khi sử dụng đo lường extremity
Gc
k
biểu thò giá trò của GC ở bước thứ k khi một extremity node I được ánh xạ .Nếu không tính
đến E
I
thì ngưỡng được khởi động giá trò 0.5 và giá trò nầy bao trùm cho tất cả những node chưa
được ánh xạ ,việc ánh xạ của node I trong trừơng hợp nầy chỉ mới là cơ sở trên GC
k
.Một số chỉ
dẫn sau :
1.ánh xạ xấu (poor mapping): Giả sửï node i là một hardware extremity .Nếu GC
k
>=0.5

,đối tượng 1 (Obj1) được chọn thời gian là tối thiểu và i có thể ánh xạ sang hardware trên cơ sở
giới hạn thời gian .Tuy nhiên i là một hardware extremity và ánh xạ nó sang hardware hiển
nhiên là sự lựa chọn xấu .
2.ánh xạ không thể thực hiện (infeasible mapping) :Giả sửï node i là một software
extremity .Nếu GC
k
< 0.5, đối tượng 2 được chọn (Obj2) không gian là tối thiểu và i có thể được
ánh xạ đến software .Node i là một software extremity ,vì vậy ánh xạ nó sang software có thể
vượt quá giới hạn cho phép .
Bao trùm lên những vấn đề nầy ,đo lường extremity E
i
được sử dụng để thay đổi ngưỡng
mặt đònh trên ánh xạ thích hợp . Ngưỡng mới là 0.5 + E
i
.GC
k
được so sánh với ngưỡng thay đổi
nầy . Trong trường hợp software extremities thì –0.5 <= E
i
<=0 ; vì vậy 0<=ngưỡng
(threshold)<=0.5. Trong trường hợp hardware extremities thì 0<=E
i
<=0.5, vì vậy 0.5<=ngưỡng
(threshold)<=1.
2.2.3.2 Local phase 2 or Repeller nodes :
GCLP sử dụng khái niệm repeller hay local phase 2 node để thực hiện việc hoán đổi
giữa hardware và software của những node tương tự .Để làm điều nầy phải đồng nhất những
thuộc tính bên trong nào đó của node (được gọi là thuộc tính repeller) nó phản ảnh sự thích hợp
có sẵn của node để ánh xạ sang hardware cũng như software .Ví dụ phép toán bit (bit operation)
được điều khiển tốt hơn trong hardware ,trong khi đó những phép toán về memory (memory

operation) thì phù hợp hơn cho software .Như vậy một node với nhiều bit điều khiển bằng tay
(bit manipulation) liên hệ đến những node khác là software repeller , trong khi một node với
nhiều phép toán bộ nhớ quan hệ đến những node khác là hardware repeller .Việc di chuyển
một node với nhiều phép toán bit điều khiển bằng tay ra khỏi software gọi là repeller force .Từ
đó tỉ lệ của phép toán bit điều khiển bằng tay trong một node gọi là thuộc tính software repeller
(software repeller property). Tương tự tỉ lệ của phép toán bộ nhớ trong một node gọi là thuộc
tính hardware repeller (hardware repeller property) .Một thuộc tính repeller được xác đònh bằng
một giá trò repeller . Kết quả kết hợp của tất cả thuộc tính repeller trong một node được biểu thò
như là sự đo lường repeller của node .Tất cả những node được xếp hàng tùy theo sự đo lường
giá trò repeller của chúng .Chẳng hạn như cho 2 node N1 và N2 với đặc điểm software tương tự
http:// www.diachiweb.com

,nếu N1 có giá trò software repeller lớn hơn N2 và 1 trong 2 được lựa chọn ánh xạ sang
hardware thì ưu tiên N1 .
Một vài thuộc tính repeller có thể được nhận dạng cho mỗi node .Hổn hợp lệnh ở mức
bit và mức độ chính xác là những ví dụ cho thuộc tính software repeller ,trong khi những hổn
hợp lệnh tập trung bộ nhớ và hổn hợp lệnh tìm kiếm trong bảng có thể là thuộc tính hardware
repeller .Mỗi thuộc tính được xác đònh bởi giá trò thuộc tính . Kết quả kết hợp của tất cả thuộc
tính repeller trong một node được biểu thò như là sự đo lường repeller của node .
Chúng ta quan tâm đến hỗn hợp lệnh cấp độ bit (bit level instruction mix) là một thuộc
tính software repeller , thuộc tính nầy được xác đònh thông qua giá trò thuộc tính của nó gọi là
BLIM.BLIM
i
được đònh nghóa là tỉ lệ của những lệnh cấp độ bit trên tổng các lệnh trong một
node i (0 <=BLIM
i
<=1).Ví dụ DAG như hình vẽ 6 (a) : node 2 trong đồ thò là bộ lọc IIR ,node 5
là bộ trộn ,ở hình (b) trình bày đồ thò giá trò BLIM cho tất cả các node trong DAG .Ở hình (a)
node 5 ,bộ trộn có giá trò BLIM cao ,node 2 bộ lọc IIR không có bất kỳ một bit điều khiển bằng
tay nào và như vậy BLIM có giá trò 0 .Node có giá trò BLIM cao sẽ xấu khi ánh xạ sang

software
BLIM
IIR

1
scrambler


Scrambler IIR
°
0 1 2 3 4 5 node in graph
(a) (b)
(hình 6) Một ví dụ của thuộc tính repeller
Quan tâm 2 node N1 , N2 với không gian software (hardware ) là as
1
(ah
1
) và as
2
(ah
2
) .
Giả sử BLIM
1
>BLIM
2
, nếu as
1
@
as

2
thì ah
1
<ah
2
(bởi vì phép toán bit làm cho không gian
hardware nhỏ hơn ). Thật vậy N1 là software repeller so với N2 trên cơ sở thuộc tính hỗn hợp
lệnh cấp bit . Khi lựa chọn ánh xạ N1 hoặc N2 sang hardware thì chọn N1 thích hợp hơn (dựa
vào thuộc tính BLIM).
Những thuộc tính repeller khác được đề cập trước đây thì xác đònh tương tự dựa vào giá
trò thuộc tính của chúng .Kết quả tích lũy các thuộc tính repeller cho một node được quan tâm
khi ánh xạ node đó . Sự đo lường repeller (repeller measure) R
i
của một node là kết quả gộp
lại các giá trò repeller của node đó .Đo lường repeller được sử dụng để thay đổi lại ngưỡng mà
GC đã so sánh khi lựa chọn mục tiêu ánh xạ .
REPELLER MEASURE :
Procedure compute_repeller _measure
Input v
i,p
= giá trò của thuộc tính repeller p của node i, i
Ỵ
N,p
Ỵ
P .
Output đo lường repeller R
i
,"i Ỵ N,0.5 <= R
i
<=0.5.

S1. tính toán cho mỗi thuộc tính p :
s
2
(v
i,p
) = sự khác nhau của v
i,p
của tất cả node i .
min (v
i,p
)= min của v
i,p
của tất cả node i .
1
3
5
4
2
http:// www.diachiweb.com

max(v
i,p
) =max của v
i,p
của tất cả node i .
để RX = RH nếu p
Ỵ
RH hay RX = RS nếu p
Ỵ
RS.



s

2
(v
i,p
)
a
p

=
= trọng của thuộc tính repeller p,
å

s

2
(a
p
) =1 .
å s
2
(v
i,p
) pỴRX
p
Ỵ
RX
S2 . tính toán giá trò thuộc tính bình thườnh nv

i,p
cho mỗi thuộc tính p của node i
v
i,p
-min(v
i,p
)
nv
i,p
= .0<=nv
i,p
<=1.
max(v
i,p
)-min(v
i,p
)
S3.tính toán đo lường repeller R
i
cho mỗi node i
R
i
= 0.5(
å
a
p.
nv
i,p
-
å

a
p.
nv
i,p
), -0.5 <=R
i
<=0.5.
pỴ RH p ỴRS
Giải thuật mô tả tính toán đo lường repeller cho mỗi node i (R
i
) .Đặt RH tập thuộc tính repeller
hardware và RS là tập thuộc tính repeller software ,P là hội của 2 thuộc tính trên
Giá trò v
i.p
của mỗi thuộc tính repeller p của node i thu được nhờ sự phân tích node
.Chẳng hạn như xem xét thuộc tính trộn lệnh mức bit (bit level instruction mix) .Các phép toán
cấp bit như là (or ,and ,exor) đầu tiên được nhận ra trong node .Giá trò BLIM của node i là tỉ lệ
của số phép toán ở mức bit trên tổng số phép toán trong node .Giá trò thuộc tính repeller khác
được tính toán tương tự .
Trong S1 của giải thuật ,mỗi giá trò thuộc tính repeller về sự khác nhau ,giá trò nhỏ nhất
và giá trò lớn nhất được tính toán . Những giá trò thuộc tính được bình thường hóa trong S2 .
Trong S3 đo lường repeller cho mỗi node được tính toán như là một tổ hợp của các giá trò thuộc
tính bình thường hóa repeller .Trọng a
p
của thuộc tính p là tỉ lệ tương ứng với giá trò khác nhau
của giá trò node đó .
Thay đổi ngưỡng khi sử dụng đo lường repeller :
Như đã trình bày trong phần trước repeller thiết lập hoán đổi để thu giảm tất cả không
gian hardware .Có thể nói rằng đo lường repeller là đo lường của sự hoán đổi lại của 2 node
của phase 2 tương tự giữa ánh xạ hardware và software .Như đã nói cho một lựa chọn ánh xạ

của 2 node sang hardware ,thì node có đo lường repeller software cao hơn sẽ được chọn .
Cho một phase 2 node i với đo lường repeller software thích đáng , giải thuật sẽ cố
gắng hoàn thành việc đẩy node i ra khỏi software .Nó thay đổi ngưỡng mà mục tiêu được lựa
chọn sẽ thuận lợi hơn để hoàn thành việc ánh xạ. Việc hoán đổi nầy giải phóng tài nguyên hiện
thời cho node chưa được sắp thứ tự với đo lường thuộc tính repeller thấp , nhờ vậy cho phép thu
giảm toàn bộ không gian hardware .
D; repeller R
i
được sử dụng để thay đổi ngưỡng ,ngưỡng mới là 0.5+R
i
.Với software
repellers thì –0.5 <=R
i
<=0 ,vì vậy ngưỡng là 0<=ngưỡng (threshold)<= 0 , với hardware
repellers thì 0<=R
i
<=0.5 vì vậy ngưỡng là 0.5<=ngưỡng <=1.
2.2.3.3 Local phase 3 hay normal nodes :
Một node không là extremity node hay repeller node thì là node bình thường (normal
node ) được gọi là lacal phase 3 .Ngưỡng được thiết lập mặc đònh là 0.5 khi ánh xạ .Như vậy
mục tiêu ánh xạ được quản lý bởi GC .
Tóm lại node được phân thành 3 loại :extremity node ,repeller node ,và normal node
.Mỗi phase thích hợp của mỗi node được xác đònh bởi sự đo lường của nó , gọi chung là local
http:// www.diachiweb.com

phase delta (D) .Trong trường hợp node là extremity node thì D=E
i
,trong trường hợp node là
repeller node thì
D

=R
i
,và trường hợp normal node thì
D
= 0 .Local phase delta được dùng để
tính toán thay đổi ngưỡng :
Ngưỡng =0.5+
D
.
2.2.4 .GIẢI THUẬT GCLP
Algorithm : GCLP
Input ah
i
,as
i
, th
i
, ts
i
, E
i
(extremity measure) ,và R
i
(repeller measure)
"
i
Ỵ
N
Giá truyền nhận :ah
comm

,as
comm
và t
comm
và giới hạn AH , AS, và D.
Output :ánh xạ M
i
(M
i

Ỵ

{
hardware,software
}
,thời gian bắt đầu t
i
,
"
i
Ỵ
N
Khởi tạo :N
u
={ nodes chưa ánh xạ } =N ,N
M
={ nodes đã ánh xạ } =f
Procedure
While { |N
u

|> 0 } {
S1 Tính toán GC
S2 Xác đònh tập node sẵn sàng N
R

S3 Tính toán thời gian thực thi kết quả t
exec
(i) cho mỗi node i
If i Ỵ N
u
t
exec
(i) =GC .th
i
+ ( 1-GC).ts
i

Else if i Ỵ N
M
t
exec
(i) = th
i
.I(M
i
==hardware ) +ts
i
.I(M
i
==software )

S4 Tính toán đường dài nhất longestpath(i),
"
i
Ỵ
N
R
sử dụng t
exec
(i)
S5 Lựa chọn node i ,i Ỵ N
R
bằng ánh xạ :max(longestpath(i))
S6 Xác đònh ánh xạ M
i
cho i :
S61 if (E
i
<> 0) D =g.E
i
(local phase 1)

g
là extremity measure weight 0<=
g
<=1
else if (R
i
<>0)
D
=

n
.R
i
(local phase 2)
n là repeller measure weight 0<=n<=1
else if
D
=0 (local phase 3)
S62 ngưỡng =0.5 +
D
,0<=ngưỡng <=1
S63 if GC >=ngưỡng m:minimize(obj1)
else m:minimize(obj2)
s64 M
i
=m ; set(t
i
) ; N
u
=N
u
\
{
i
}
; N
M
ß
{
i

}

update (T
remaining
,AH
remaining
,AS
remaining
);
}
Giải thuật ánh xạ mỗi node ở một bước .Bước S1 Gc được tính toán và .Ở bước S2 xác
đònh tập node sẵn sàng nghóa là tập những node chưa được ánh xạ mà tiền bối của nó đã được
ánh xạ ,một trong những node sẵn sàng nầy sẽ được chọn để ánh xạ trong bước 5 .Đặc biệt nên
chọn node trên đường dài nhất của graph ,đường tới hạn chung bao gồm những node chưa ánh
xạ tính toán nó .Ở bước S3 tính toán thời gian thực thi đến kết quả của node i .Ở bước 4 tính
toán con đường dài nhất sử dụng thời gian thực thi đến kết quả của node i .Ở bước 5 lựa chọn
node i cho ánh xạ .Ở bước 6 xác đònh ánh xạ M
i
cho mỗi node i ,nếu node là extremity node
(hay repeller node ) thì dùng để thay đổi ngưỡng .Sự góp phần của đo lường extremity và
repeller có thể thay đổi bởi trọng
g
và v .Mục tiêu ánh xạ được lựa chọn nhờ vào việc so sánh
lại GC với ngưỡng .Nếu thời gian là tới hạn thì mục tiêu thời gian hoàn thành nhỏ nhất sẽ được
chọn , khác đi thì tiêu thụ tài nguyên nhỏ nhất được chọn .
Obj1 :t
fin
(i,m) ,trong đó mỴ {hardware ,software }
T
fin

(i,m) =max(max
p(i)
(t
fin
(p) +t
c
(p,i)),tf
last
(m))+t(i,m)
Trong đó :
http:// www.diachiweb.com

P(i) : tập tiền bối của node i ,p Ỵ P(i)
t
fin
(p) :thời gian hoàn thành của tiền bối p
t
c
(p,i) =thời gian truyền nhận giữa node tiền bối p và node i
tf
last
= thời gian hoàn thành của node cuối được gán bởi ánh xạ m =0 nếu m là hardware .
t(i,m) = thời gian thực thi của node i trên ánh xạ m

(as
i
+as
comm
tot
) (ah

i
+ah
comm
tot
)
Obj2 : .I(m=software ) + .I(m=hardware )
AS AH
remaining


Obj1 lựa chọn ánh xạ mà thời gian hoàn thành nhỏ nhất của node .Một node chỉ bắt
đầu thực thi sau khi tất cả các tiền bối của nó hoàn thành việc thực thi và dữ liệu đã được truyền
đến nó từ các tiền bối cũng vậy một node không thể bắt đầu thực thi trên một tài nguyên
software cho đến khi node cuối cùng được ánh xạ sang software hoàn thành việc thực thi .
Obj2 sử dụng đo lường số phần trăm tiêu thụ (percentage resource consumption) .Việc
đo lường nầy là phần nhỏ của không gian tài nguyên của một node (vùng không gian truyền
nhận ) trên tổng không gian tài nguyên .không gian ah
comm
tot
(as
comm
tot
) đưa vào tính toán giá
tổng cộng của sự truyền nhận (kết nối trong hardware và code trong software ) giữa node i trong
hardware (software ) và tất cả tiền bối của nó .Tài nguyên hardware là không gian tài nguyên
yêu cầu bởi node được chia xẽ bởi không gian hardware còn lại (AH
remaining
).
2.2.5 Tóm tắt giải thuật GCLP :
Cho đến đây chúng ta đã bàn luận giải thuật GCLP (global criticality /local phase ) để

giải quyết vấn đề phân chia nhò phân (P
1
) điểm chính yếu của giải thuật được tóm tắt như sau :
Giới hạn chung là một đo lường nhìn trước chung mà để xác đònh thời gian giới hạn ở
một bước của giải thuật đưa vào tính toán những node chưa ánh xạ hiện thời .GC so sánh với
ngưỡng để lựa chọn mục tiêu ánh xạ ở mỗi bước của giải thuật .Những node sử dụng số lượng
tài nguyên không cân đối trong khi ánh xạ sang hardware hay software thì được phân loại thành
extremities .Ngưỡng sử dụng để ánh xạ những node nầy được thay đổi để tính toán cho những
ánh xạ thích hợp .Tổng không gian hardware được thu giảm tốt hơn bởi việc sử dụng khái niệm
hoán đổi những node repeller (on line swaps between repeller node ). Repeller node được
phân loại và xác đònh trên cơ sở những thuộc tính bên trong của node .Ngưỡng được sử dụng cho
ánh xạ những node repeller được thay đổi cho phù hợp với quan hệ ánh xạ của nó .Giải thuật
có độ phức tạp (O(|N|
2
)) với kết quả so sánh là tối ưu .
Trở về trang chu
2.3 Phân chia mở rộng (Extended partition )
2.3.1 Giớùi thiệu :
Lý do cho việc giải quyết vấn đề phân chia mở rộng là do tính mềm dẽo của việc chọn
lựa một hướng hiện thực cho node thay vì phải cố đònh cách hiện thực , nhờ vậy mà nó có thể
thu giảm được không gian hardware hay thời gian thực thi software . Từ thực tiển trong việc
tổng hợp người ta thấy rằng kết quả của hiện thực hệ thống tốt hơn khi có phân chia mở rộng .
2.3.2 Giải thuật phân chia mở rộng :Mục tiêu thiết kế .
Giải thuật GCLP giải quyết vấn đề phân chia nhò phân P1 .Vấn đề phân chia mở rộng P2
đề cập đến tối ưu hoá việc ánh xạ như ‘implementation bin ‘(tạm dòch là ‘hiện thực bin’) cho
mỗi node .Quan tâm hiện thực bin được trình bày theo hình vẽ 7
http:// www.diachiweb.com















Hình7 NH
i
tập của hardware trong hiện thực bin
CH
i
=
{
(ah
i
j
/th
i
j
) j
Ỵ
NH
i

}


Biểu thò L là nhanh nhất (bên trái nhất của hiện thực bin ) và H là chậm nhất (bên phải nhất của
hiện thực bin) .Như vậy đường cong hiện thực bin đi qua từ L đến H ,không gian hardware yêu
cầu hiện thực node được làm giảm .Từ quan điểm tối thiểu không gian hardware mỗi node
được ánh xạ sang hardware có thể ở tập H bin (không gian nhỏ nhất).Tuy nhiên không thể từ
tập H đáp ứng hiện thực chậm nhất .Vấn đề phân chia mở rộng được lựa chọn một sự thích hợp
hiện thực bin và phép ánh xạ cho mỗi node như tổng không gian hardware nhỏ nhất có tính đến
giới hạn về thời gian và tài nguyên .Vấn đề nầy rõ ràng phức tạp hơn ánh xạ phân chia nhò phân
.Đích của chúng ta là thiết kế một giải thuật hiệu quả giải quyết vấn đề phân chia mở rộng .Có
2 mục tiêu đi đến việc thiết kế
1.Mục tiêu thiết kế 1 :Hợp lý hoá tỉ lệ phức tạp .
Vấn đề phân chia nhò phân có 2
|N|
khả năng ánh xạ ,N là số node trong đồ thò .Với B
hiện thực bin bên trong 1 ánh xạ ,vấn đề phân chia mở rộng có (2B)
|N|
khả năng trong trường
hợp tồi nhất .Độ phức tạp của giải thuật không tỉ lệ với kích thước (số lựa chọn thiết kế trên một
node )của quá trình phân chia .Nếu giải thuật phân chia nhò phân có độ phức tạp O(|N|
2
) thì giải
thuật phân chia mở rộng không thể có độ phức tạp O(|N|
2B
) ,B là mẫu trong tầm từ 5-> 10.Rõ
ràng giải thuật phân chia nhò phân không thể mở rộng để trực tiếp giải quyết vấn đề phân chia
mở rộng vì bùng nổ khả năng hiện thực .
2.Mục tiêu thiết kế 2 :Dùng lại GCLP.
Chúng ta đã có một giải thuật hiệu quả cho phân chia nhò phân , giải thuật phân chia mở
rộng dùng lại nó . Điều nầy đề nghò phân chia mở rộng được tách thành 2 khối :ánh xạ và lựa
chọn hiện thực bin .GCLP có thể sử dụng cho ánh xạ .

Mục đích trên vẫn không đầy đủ tuy nhiên phân tích vấn đề phân chia mở rộng theo 2
bước độc lập :cụ thể là việc ánh xạ theo sau là lựa chọn hiện thực bin .Duyệt qua các node
trong đồ thò có nghóa hiện thực bin của một node riêng biệt ảnh hưởng đến việc ánh xạ của
những node chưa được ánh xạ .Từ đây có sự tương quan giữa việc ánh xạ và lựa chọn hiện thực
bin ,nó không thể tối ưu trong cô lập giữa ánh xạ và hiện thực .Điều đòi hỏi nầy phải được giữ
trong giải thuật .Hướng đi của chúng ta là giải quyết vấn đề phân chia mở rộng được tóm tắt
trong hình 8

area






ah
i
j




L bin th
i
j
H bin

time



http:// www.diachiweb.com

Free nodes = N




nh xạ cho tất cả node tự do













|N|lần
n

y ánh xạ ,thứ tự và hiện thực bin
cho tất cả các node


hình 8 :hướng đi MIBS giải quyết phân chia mở rộng
Heuristic được gọi là MIBS .Kết quả cuối cùng mỗi node trong dồ thò có đặc điểm bởi 3

thuộc tính :việc ánh xạ ,hiện thực bin ,thứ tự node .Khi tiếp diễn giải thuật đòi hỏi mở rộng
thông tin phát sinh ra ,mỗi node trong DAG qua tuần tự 3 trạng thái :1-tự do (free node ) , 2-đònh
danh (tagged node ),3-cố đònh (fixed node ) .Trước khi giải thuật bắt đầu 3 thuộc tính thì chưa
biết ,như vậy những node được gọi là node tự do .Công nhận rằng không gian và thời gian trung
bình GCLP được áp dụng đầu tiên để ánh xạ và tuần tự tất cả các node thay đổi trong đồ thò
.Một node tự do riêng biệt (gọi là node đònh danh tagged node ) sẽ được lựa chọn sau đó ,và
một hiện thực thích hợp bin được lựa chọn sau cho node đònh danh .Trong phần sau mô tả một
thủ tục lựa chọn một bin , nó xác đònh việc hiện thực bin cho node đònh danh .Một lần ánh xạ và
hiện thực bin đã biết ,node đònh danh trở thành node cố đònh .GCLP được áp dụng cho những
node còn lại và quá trình nầy được lặp cho đến khi tất cả node trong DAG trở thành cố đònh
(fixed node ) . Giải thuật MIBS có |N| bước cho |N| node trong DAG .
Hướng đi của MIBS tích lũy chặt chẽ ,vạch ra mục tiêu thiết kế :GCLP và lựa chọn bin
áp dụng xen kẽ bên trong mỗi bước của giải thuật MIBS ,có tiếp diễn quay lui giữa ánh xạ và
hiện thực bin .Giải thuật MIBS có độ phức tạp O(|N|
3
+B|N|
2
) ,trong đó B là số hiện thực bin trên
ánh xạ .
2.3.3 Lựa chọn hiện thực bin (implementation bin ) :
2.3.3.1 Tổng quát :
Tính toán ánh xạ và thứ tự cho những node tự do
- Thiết lập giá trò không gian và thời gian trung bình

- p dụng GCLP

Lựa chọn node danh hiệu T với ánh xạ M
T

Tìm hiện thực bin cho T bên trong ánh xạ M

t

Free = Free \ T
Fixed ß T
Update(schedule)
Free = rỗng
http:// www.diachiweb.com

Chỉ giới hạn vấn đề lựa chọn hiện thực bin cho những node hardware . Những khái niệm
trình bày ở đây có thể mở rộng lựa chọn hiện thực bin ở software . Từ hình trên trong mỗi bước
của giải thuật MIBS thì GCLP áp dụng trước xác đònh ánh xạ lặp lại của những node tự do
.Những node tự do được ánh xạ đến hardware tại bước hiện thời gọi là free
h
node . Một node
đònh danh được lựa chọn từ tập free
h
node ,công nhận rằng việc ánh xạ được xác đònh bởi GCLP
,còn thủ tục lựa chọn bin được áp dụng để lựa chọn một hiện thực bin cho node đònh danh . Hình
9 trình bày dòng chảy của thủ tục lựa chọn bin .Ý tưởng chính là dùng đo lường trước tương
quan giữa hiện thực bin của node đònh danh với không gian hardware yêu cầu cho free
h
node
,nó lựa chọn một đáp ứng tốt nhất cho hiện thực bin .
Tính toán đo lường trước rất phức tạp ,để đơn giản ta công nhận rằng free
h
node có thể
hoặc L hay H bin .Tất cả free
h
node công nhận khởi tạo từ H bin của chúng .Những tính toán đo
lường trước (được gọi là bộ phận bin BF

T
j
bin fraction)
Cho mỗi node bin j của node đònh danh T,phần nhỏ của free
h
node cần di chuyển từ H bin đến L
bin theo thứ tự ràng buộc thời gian .Một giá trò cao của BF
T
j
chỉ thò rằng nếu node đònh danh T
được hiện thực trong bin j ,một bộ phận lớn của free
h
node tìm được ánh xạ hiện thực nhanh (L
bin) từ đó làm tăng không gian toàn bộ . Đường cong bộ phận bin (BFC
T
) là tập hợp tất cả giá
trò bộ phận bin của node đònh danh T .
Độ nhạy của bin (Bin sensitivity) :
Là độ dốc của BFC
T
nó phản ánh đáp ứng của bộ phận bin trong di chuyển của node T
,giả thiết rằng độ dốc lớn nhất của đường cong bộ phận bin là trong khoảng từ k-1 đến k . Việc
di chuyển của node đònh danh từ bin k-1 đến k là sự thay đổi lớn nhất của free
h
node đến L bins
của chúng tương ứng từ kàk-1 của node đònh danh ,kết quả là làm giảm lớn nhất của không
gian free
h
node . Từ đó bin thứ k-1 được lựa chọn như là hiện thực bin cho node đònh danh (B
T

*
)
.Tính toán BFC và độ nhạy bin được mô tả tiếp theo .
Những ghi chú dùng trong thủ tục lựa chọn bin tóm tắt trong bảng 10










1
BFC
T

fixed node
tagged node free node 0
L
T
K-1 K H
T


BS


L

T
H
T

Tính toán bộ phận bin (BFC
T
)
Tính toán độ nhạy bin
http:// www.diachiweb.com

area
B
T
*

B
T
*
time



Hình 9(thủ tục lựa chọn bin)

Ký hiệu Giải thích
T Node đònh danh (tagged node )
Fixed nodes Node cố đònh
Free nodes Node tự do chưa được ánh xạ
Free
h

nodes Node tự do được ánh xạ đến hardware bằng
GCLP tại mỗi bước của giải thuật MIBS
CH
T
(CS
T
) Đường cong hardware ,software cho node T
NH
T
(NS
T
) Tập hiện thực bin software,hardware của
node T
L
T
(H
T
) L (H) bin của node T.L (H) là nhanh nhất
(chậm nhất) của bin
B
T
*
Lựa chọn hiện thực bin cuối cùng cho node T
BF
T
j
Bộ phận bin được tính toán khi node T được
hiện thực trong bin j
BFC
T

Đường cong bộ phận bin của node T
BS
MAX
Giá trò lớn nhất của độ nhạy bin
Hình 10 :tóm tắt ký hiệu sử dụng trong giải thuật lựa chọn bin
2.3.3.2 Đường cong bộ phận bin (BFC):
Công nhận rằng node T đã được hiện thực trong bin j ,BF
T
j
được tính toán như bộ phận
của free
h
node ,nó phải di chuyển từ H bin đến L bin theo thứ tự thực hiện .Đường cong bộ phận
bin BFC
T
đánh dấu của bộ phận bin BF
T
j
của mỗi bin j của node đònh danh T. Thủ tục tính toán
BFC được mô tả kế tiếp .Những khái niệm cơ sở tương tự sử dụng trong tính toán GC ,để đơn
giản ta áp dụng thủ tục lựa chọn bin cho node đònh danh được ánh xạ đến hardware bởi GCLP .
Một hiện thực bin đơn được công nhận khi node đònh danh được ánh xạ sang software
Procedure compute_BFC
Input N
fixed
={ fixed nodes }.N
free
h
={free
h

nodes }.
T = tagged node ,với ánh xạ M
T
(hardware công nhận).
Đường cong hiện thực hardware CH
T
.
Output BFC
T
=
{
(BF
T
j
,j),
"
j
Ỵ
NH
T
}

Khởi tạo : N
H
à
L
= f , t
exec
(p) biết với tất cả các node cố đònh ,pỴN
fixed

.
For (j=1;j<= |NH
T
| ; j++)
{

S1 Thiết lập , t
exec
(T)=thï
T
j

S2 for tất cả kỴ N
free
h
,thiết lập , t
exec
(k) = th
k
H
(tất cả free
h
nodes ở H bins)
S3 Tính toán T
finish
, cho ánh xạ và , t
exec
cho tất cả nodes
S4 Tìm trong tập N
H

à
L
của free
h
nodes được di chuyển đến L bin trong thứ tự gặp đường giới
hạn
Lựa chọn bin (B
T
*
)
http:// www.diachiweb.com

S41 N
H
à
L
ß next(N
free
h
)
S42 , t
exec
(f) =th
f
L
,
"
f
Ỵ
N

H
à
L

S43 Cập nhật (T
finish
)
S44 if T
finish
> D goto s41

å size
i

i
Ỵ
N
H
à
L

S5 BF
T
i
=

, 0 <=BF
T
j
<=1


å
size
i

i Ỵ N
free
h


Từ s1 đến s5 dùng để tính toán bộ phận bin BF
T
j
cho một bin riêng biệt j .N
fixed
là tập node cố
đònh và N
free
h
là tập node tự do ánh xạ sang hardware bởi GCLP tại bước hiện hành của giải
thuật MIBS.Trong S1 thời gian thực thi của node đònh danh được thiết lập bằng thời gian thực thi
của bin thứ j . Trong S2 thời gian thực thi cho tất cả các node free
h
được thiết lập tương ứng với
từng bin H .Thời gian hoàn thành cho DAG (t
finish
) được tính toán trong S2 .Trong S4 tính toán
N
H
à

L
,tập free
h
node được di chuyển đến bin L của chúng theo thứ tự ràng buộc thời gian .
Những chức năng bình thường khác có thể sử dụng theo thứ tự free
h
node .Rõ ràng việc lựa
chọn xếp loại node theo thứ tự làm giảm thời gian thực thi H của H bin . Một khả năng thứ hai
có thể sử dụng là dùng (th
i
H
/ th
i
L
) như là một chức năng để xếp loại node .Điều nầy có kết quả
di chuyển những node lấy lại lớn nhất về thời gian khi di chuyển từ H đến L bin .
BF
T
j
thì được tính toán trong S5 bằng tỉ số của tổng kích thước của những node N
H
à
L
trên
tổng của kích thước của node trong N
free
h
.Có thể nói rằng kích thước của node là số phép toán
cơ bản (nguyên tố) như (cộng ,nhân …) trong node .
Trong phần tóm tắt một giá trò cao của mẫu bin cho node T được chỉ thò lựa chọn hiện

thực bin thứ J .Giống như kết quả trong phần lớn của free
h
node được thiết lập khởi động tuần tự
đến những bin L.
2.3.3.3 Lựa chọn Implementation bin :
Hình 11a trình bày một đồ thò đường cong kiểu mẫu bin của một node đònh danh T
L
T
(H
T
) biểu thò L(H) bin cho node T >điều mong muốn là bin B
T
*
được lựa chọn như thế nào
cho node nầy .Một cách trực quan B
T
*
= H
T
,từ đó điều nầy cho không gian hardware là nhỏ
nhất cho node T ở H
T
.Tuy nhiên BF
T
H
thì cao ,một bộ phận lớn của node free
h
thì trong L bin vì
vậy tổng không gian hardware có thể không cần lớn ,khi node đònh danh dòch từ H
T

bin đixuống
,kết quả làm giảm trong BF ngụ ý rằng bộ phận của node free
h
ở L bin giảm và tuần tự cho
phép không gian hardware của node free
h
giảm .Độ dốc của BFC
T
đại diện cho không gian bin
được làm giảm nhanh như thế nào của node free
h
trong node T.Độ dốc nầy gọi là độ nhạy bin
BS ,nó phản ánh mối tươmg quan giữa sự di chuyển bin của node đònh danh và tổng không gian
được làm giảm của free
h
node co nghóa BS
T
j
=BF
T
(j+1)
–BF
T
j
,L<=j<= H-1; trong đó BS
T
H
= 0 .
Hình 11b BS
max

, IB(B
T
*
) cho node đònh danh T được lựa chọn là bin với độ nhạy =
BS
max
, nếu BS
max
>0 .Nếu BFC
T
là hằng số (hình 11c) thì BS
max
= 0 và node đònh danh được ánh
xạ sang H bin của nó .Từ đây di chuyển nó từ chậm nhất đến hiện thực nhanh nhất không ảnh
hưởng đến những node free
h


(a) (c)

BFC
T
BF
T
H
BFC
T