http:// www.diachiweb.com

Ta thấy đối với ánh xạ và thứ tự thì thời gian tính toán là hằng .Do vậy tổng dộ phức tạp của
giải thuật GCLP ở mổi bước là O(N+A).gi thuật chạy N lần vậy tổng thời gian là
O(N.(N+A)).kiểu mẩu cho ứng dụng DSP thì A»N như vậy độ phức tạp xấu nhất của giải thuật
GCLP là O(N
2
)
3.Phân tích độ phức tạp cuả giải thuật Bin selection procedure
Độ phức tạp của giải thuật được tính toán như sau:
COMPLEXITY(BIN SELECTION)
S1.Tính toán BFC(Bin Selection Curve):O(B*(N+A))
S1.1.Cho mỗi BIN tính toán BIN FRACTION:O(N+A)
S1.1.1.Lượng giá những node di chuyển đến L bin
S1.1.2.Tính toán thời gian hoàn thành chính xác công nhận ánh xạ này và lựa chọn
bin
S2.Tính toán độ nhạy bin:O(B)
S3.Tính trọng cuả độ nhạy bin:O(B)
S4.Lựa chọn bin
Sự tính toán BIN FRACTION trong bước S1.1 thì tương tự như sự tính toán trong GC.Ở đây
độ phức tạp của giả thuật BIN FRACTION cho một BIN đặt biệt là O(N+A).Độ phức tạp
của bước S1 ở đây là O(B*(N+A)) cho B implementation bin.Độ phức tạp của những bước
khác thì đơn giản là thứ tự của số bin.Vậy độ phức tạp của giải thuật ở đây là:O(B.(N+A)).
4.Phân tích độ phức tạp của giải thuật MIBS(Mapping and Bin
Seclection)
Giải thuật MIBS áp dụng GCLP lựa chọn bin N lần cho tất cả những node trên graph.Độ
phức tạp của những bước nhỏ được tính toán như sau:
COMPLEXITY(MIBS)
S1.Xác đònh ánh xạ cho tất cả các các node free bằng cách chạy
GCLP:O(N
2

).
S2.Xác đònh những node sẳn sàng:O(N)
S3.Chọn node tagged :O(N).
S4.Tính toán hiện thực BIN cho node tagged sử dụng giải thuật BIN
SELECTION :O(B*(N+A))
Độ phức tạp của mổi bước cuả giải thuật là:O(N
2
+B.N).Mỗi bước lập lại N lần cho N node
.Vậy độ phức tạp của giải thuật là:O(N
3
+B*N
2
)
5. Giải thuật phát sinh DAG ngẫu nhiên :
Procedure Generate_random_Graph /* phát sinh thông số cho DAG */
Input : kích thước của đồ thò N
Output : Đồ thò lặp vòng trực tiếp , các cạnh không song song
S1 . a= random_int(N,N
2
) (số cung )
S2 . phát sinh hoán vò ngẫu nhiên 1 N trong dãy “perm”
S21 .for(i=0;i<N;i++) {perm[i]=i}
S22. For(i=0;i<N;i++){
S221.j=random_int(0,N-1);
S222.tmp=perm[i]
S223.perm[i]=perm[j];
S224. Perm[j]=tmp;
}
http:// www.diachiweb.com


S3 phát sinh cạng A từ (perm[i],perm[j]),i<j
For(i=0;i<A;i++){
Src=ramdom_int(0,N-2);
Dest=random_int(src+1,N-1);
If(!existsarc(src,dest)) add_arc(src,dest);
}
S4 phát sinh thông tin bên trong cho mỗi node i :size
i
,ts
i
.th
i
,as
i
,ah
i
.
S41. Xác đònh nếu node i là extremity node ,repeller node hay normal node
S411.y=ran1();
S412. If((y>=0)&&(y<0.33)) i:extremity node
S413. If((y>=0.33)&&(y<0.66)) i:repeller node
S414. If((y>=0.66)&&(y<1)) i:normal node
S42. Thiết lập không gian và thời gian cho node i ;
S5.phát sinh những ràng buộc :T,AH,AS
S51.T=random_int(sum_th,sum_ts);
S52.AH=random_int(ah_low,ah_high);
S53.AS=random_int(as_low,as_high);
Procedure Generate_extremity_node
Input :ts
min

,as
min
,th
min
,ah
min
, ts
max
,as
max
, th
max
, ah
max
,cutoff threshold
Output : ts, th ,ah, as
S1.tính toán giá trò threshold ts
th
,as
th ,
th
th
,ah
th
(ví dụ :ts
th
=ts
min
+ cutoff* (ts
max

–ts
min
))
S2 tính toán giá trò extremity max ,min
S21. xs
max
=ts
max
/ah
min

S22. xs
min
=ts
th
/ah
th

S23.xh
max
= ah
max
/ts
min

S24.xh
min
=ah
th
/ts

th

S25.delta
h
=xh
max
–xh
min

S26.delta
s
=xs
max
–xs
min

S3 xác đònh nếu node là hardware extremity hay software extremity
S31.z=ran1();
S32.if(z,0.5) hardware_extremity ;else software_extremity ;
S4.phát sinh đo lường extremity trong khoảng (0,0.5);
S5.if hardware extremity
S51.ah=random_int(ah
th
,ah
max
);
S52.ts=ah/((2*delta
h
*ex) +xh
min

);
S53.as=random_int(as
min
,as
th
);
S54.th=random_int(th
min
,th
th
);
S6.if software extremity :
S61.ts=random_int(ts
th
,ts
max
);
S62.ah=ts/((2*delta
s
*ex) +xs
min
);
S63.as=random_int(as
min
,as
th
);
S64.th=random_int(th
min
,th

th
);

Procedure Generate_repeller_node
Output: ts,th, as,ah;
http:// www.diachiweb.com

S1.phát sinh dãy giá trò TS,TH
S2.xác đònh nếu node là software repeller hay hardware repeller
S21.z=ran1();
S22if(z<0.5) hardware repeller ;else software repeller ;
S3.phát sinh đo lường repeller trong khoảng (0,0.5)(r=ran(0,0.5))
S4.if software repeller :
S41.ts=TS[random_int(0,5)];
S42.as=ts/2;
S43.ah=(1-r)*as;
S44.th=(1+ran1())*ah;
S5. If hardware repeller :
S51.th=TH[random_int(0,5)];
S52.ah=ah/2;
S53.as=(1-r)*ah;
S54.ts=(1+ran1())*th;
Procedure Generate_normal_node
Output ts,th , ah , as
S1.ts= random_int(ts
min
, ts
th
)
S2.as= ts/2

S3.th=ts/random_int(1,4)
S4.ah=th/2;

2.1 Một số thông số ban đầu :
·
Một DAG gồm :
N : tập node
A :tập cung
·
D :thời gian giới hạn khi thực thi
· AS :Dung lượng bộ nhớ,kích thước software không được vượt quá AS
·
AH :Không gian cho phép của hardware ,tổng không gian của các node hardware không
vượt quá AH .
·
ah
comm
:Không gian hardware yêu cầu truyền nhận dữ liệu .
·
as
comm
:Không gian software yêu cầu để truyền nhận dữ liệu .
·
t
comm
:Số chu kỳ yêu cầu cho truyền dữ liệu .

Trở về trang chủ
2.2 Phân chia nhò phân (binary partitioning) :
Vấn đề phân chia nhò phân (P1) :Cho trước một DAG ,lượng giá không gian ,thời gian

các node ánh xạ sang hardware ,software ,giá thông tin truyền nhận ,thời gian giới hạn thực thi
D. Mi là ánh xạ node i sang hardware hay software ,t
I
là thời gian bắt đầu của một node ,kết
quả cho được tổng không gian hardware là nhỏ nhất. Số trạng thái lớn nhất là O(2
|N|

)
Vấn đề ánh xạ sang hardware ,software và sắp xếp thứ tự có thể thành công thức như
một chương trình tuyến tính (ILP :integer linear program) và được giải quyềt một cách chính
xác ,nhưng những công thức nầy khó đúng cho những ứng dụng có kích thước vừa phải .Một số
heuristic cho phép gi quyết những khác nhau cuả vấn đề nầy
·
Giải thuật phân chia nhò phân :GCLP Algorithm
http:// www.diachiweb.com

2.2.1 Cơ sở giải thuật :
Cơ sở thứ tự khung công việc trong giải thuật GCLP dựa vào thứ tự duyệt qua một lượt
các node từ node nguồn ,với mỗi node chọn ánh xạ mà nó làm nhỏ nhất mục tiêu . P1 có các
mục tiêu :thời gian hoàn thành của node là nhỏ nhất (tổng thời gian bắt đầu và thời gian thực thi
) hay là không gian nhỏ nhất của mỗi node (không gian hardware hay kích thước của software
).Vấn đề đạt được các mục tiêu nầy có tính tương đối .
Giải thuật GCLP nó lựa chọn và chuyển đổi mục tiêu ở mổi bước để xác đònh ánh xạ và
trình tự














GC
Glocal (time)
Criticality
measure


D
Local phase delta
1.GC (Global criticality) :là sự đo lường trước mà nó lượng giá thời gian giới hạn ở mỗi
bước của giải thuật .GC sosánh với ngưỡng để xác đònh nếu thời gian là tới hạn .Nếu thời gian
là tới hạn , mục tiêu nhiệm vụ là thời gian hoàn thành nhỏ nhất được chọn ,nếu không thì
không gian nhỏ nhất được chọn .GC có thể thay đổi ở mỗi bước của giải thuật .
2.Pha cục bộ (local phase):LP là một sự phân loại của những node trên cơ sở tính đồng
nhất và thuộc tính bên trong của chúng .Mỗi node được phân loại như extremity (pha 1),hay
repeller (pha 2), hay normal (pha 3).Một sự đo lường gọi là delta pha cục bộ xác đònh số lượng
ánh xạ cục bộ thích hợp của node để ý đến sự thay đổi ngưỡng được dùng trong so sánh GC
.Lưu đồ giải thuật như sau :







Obj1
y Min(finish time)

n
Obj2
Min(% resource consumed )
threshole

0.5

>?
+
http:// www.diachiweb.com






















N
U
=N , N
M
=Þ





i














|N| times no




Compute GC
Identify local phase
And compute delta
Select mapping Mi find
Start time Ti
N
M
{I}, N
U
=N
U
\ {I}
Update (T
remaining
)
NU =Þ?
Select node among
ready nodes
Select objective
http:// www.diachiweb.com

{M
i
,t
i
}


(hình 3) Giải thuật GCLP
N là tập nodes của DAG .
N
U
là tập nodes chưa được ánh xạ được tính lại tại mỗi vòng lặp .
N
M
là tập nodes được ánh xạ .
N
U
ban đầu được gán là N. N
M
ban đầu được gán là rổng .
Mỗi vòng lặp sẽ ánh xạ một node ,bước đầu tiên của mỗi vòng lặp thời gian giới hạn chung GC
được tính toán lại trên cơ sở yêu cầu giới hạn của những node đã được ánh xạ và chưa được ánh
xạ .Quá trình được lặp N lần cho đến khi không còn node nào chưa được ánh xạ .

2.2.2 :Giới hạn chung GC :
GC là sự đo lường trước mà nó lượng giá thời gian giới hạn ở mỗi bước của giải thuật . Để hiểu
vấn đề nầy ta xét ví dụ sau :








D
H u


(a1)
u

s
s

N
M
:những nodes được ánh xạ {1,2,3}.
N
U
:những nodes chưa được ánh xạ {4,5}
S:software ,h:hardware .D thời gian giới hạn chung .





(a2)
Hardware

times

1
3
5
4
2
1

3

2
http:// www.diachiweb.com

Software
T rem
D



·
T rem :thời gian còn lại (remaining time)

N
S
à
H

b)
Hardware


times

Software
T rem
D Ts

·

Ts thời gian chạy của node được ánh xạ sang software

N
S->H
là tập của những node được ánh xạ chuyển từ software sang hardware do vượt quá thời
gian giới hạn D .

(c)
Hardware


times

Software Th
T rem
D
Hình 4

·
T h :thời gian hoàn thành nếu node chuyển từ software sang hardware và được ánh xạ sang
hardware

å size
I

i
Ỵ
N
s->H


GC= 0<= GC <=1

å
size
I

i
Ỵ
N
u

Ở mỗi bước các node đang chuẩn bò được ánh xạ sang hardware hay software .Sử dụng trình tự
nầy vàø thời gian giới hạn D ,để đầu tiên xác đònh Trem.Bước tiếp theo tất cả các node chưa
1
3

2
4 5
1 3

2
4
5
http:// www.diachiweb.com

được ánh xạ (node 4 và node 5 trong ví dụ ) sẽ được ánh xạ sang software ,lúc nầy thời gian Ts
sẽ được tính toán .Giả sử rằng Ts vượt qua giới hạn D.Một số node trong tập node chưa được
ánh xạ phải di chuyển từ software sang hardware để thỏa mãn nhỏ hơn giới hạn D .Những node
nầy tạo thành tập N
S->H

(trong ví dụ tập nầy là {5} ).Lúc nầy thời gian hoàn thành Th được tính
toán lại .Trong giải thuật GC tại một bước nào đó có thể có nhiều node chưa được ánh xạ và
cần phải ánh xạ sang hardware vì vậy phải tìm kết quả khả thi ,(thời gian như là tài nguyên
đang bò tranh chấp ).
Giải thuật tính toán GC :
Procedure Compute_GC ;
Input :N
M
,N
U
,D ,t
si
,t
hi
.size
I
,với mọi I thuộc N;
Output GC
S1 :tìm tập N
S->H
của những node chưa được ánh xạ mà có thể chuyển tư software sang
hardware để thỏa mãn giới hạn D;
S11 Lưạ chọn những node trong N
U
,dùng ưu tiên Pf di chuyển từ software sang
hardware .
S12 Tính toán thời gian Thiết kế trên cơ sở node trong tập N
S->H
được ánh xạ sang
hardware

S13 Nếu Th > D quay lại S11




å
size
I

iỴN
s->H

S2 GC= 0<= GC <=1

å
size
I

iỴN
u

Trong S11 tập những node được chọn di chuyển sang hardware trên độ ưu tiên pf .một cách rõ
ràng pf là những node nầy được sắp xếp theo thứ tự giảm dần của ts
I
(thời gian thực thi bằng
software .Một khả năng thứ hai là sử dụng tỉ số (ts
i
/th
I
) để xếp thứ tự ưu tiên các node .Điều nầy

cho kết quả tốt nhất về thời gian khi di chuyển sang hardware .Khả năng thứ ba là sắp xếp các
node theo chiều tăng của ah
I
,những node có không gian hardware nhỏ hơn sẽ được di chuyển
khỏi software đầu tiên .Kinh nghiệm chỉ ra rằng tỉ số (ts
i
/th
I
) cho kết quả tốt nhất .
S12 được xác đònh hoặc di chuyển node trong tập N
s->h
đến hardware để thỏa mãn T
H

.thời gian hoàn thành là O(|A| + |N|)
GC được tính toán trong S2 là tỉ số của tổng kích thước của những node trong tập N
s->H

và tổng kích thước trong tập N
u
.kích thước của node được xem như số các phép toán nguyên tố
(cộng ,nhân,…) trong node .Mỗi node được đại diện bởi kích thước của nó từ những node có thể
không đồng nhất trong tổng thể .
GC đo lường thời gian giới hạn chung .GC có thể giải thích bằng một cách khác : nó đo
lường khả năng (nói đơn giản) là bất cứ node không ánh xạ thì ánh xạ sang hardware .khả năng
nầy có thể thay đổi ở mỗi bước của giải thuật .
2.2.3 Pha cục bộ (Local phase) :
GC là một đo lường trung bình trên tất cả những node chưa ánh xạ ở mỗi bước .Điều nầy
làm giảm tính chính xác đến thuộc tính cục bộ của node đang được ánh xạ .Để nhấn mạnh đặc
http:// www.diachiweb.com


trưng cục bộ của những node , người ta chia làm 3 loại : extremities (gọi là local phase 1) ,
repellers (gọi là local phase 2) , normal (gọi là local phase 3).
2.2.3.1 Local phase 1 (extremity nodes )
Những node sử dụng nhiều tài nguyên không cân đối khi ánh xạ so với ánh xạ khác được
gọi là extremities .Chẳng hạn như một hardware extremity yêu cầu không gian rộng lớn khi ánh
xạ sang hardware nhưng có thể hiện thực bằng software với giá không đắt .Việc ánh xạ thích
hợp của những node như vậy được xác đònh bởi extremity measure , làm thay đổi ngưởng dùng
trong sosánh GC .
Một hardware extremity node là node sử dụng không gian lớn trong hardware , nhưng
thời gian trong software tương đối nhỏ .
Một software extremity node là node sử dụng nhiều thời gian trong software nhưng sử
dụng không gian nhỏ khi ánh xạ sang hardware . Việc di chuyển hardware extremity node sang
software extremity node hay ngược lại là rõ ràng cần thiết .
Sự chênh lệch trong sử dụng tài nguyên của extremity node I được xác đònh bởi
extremity measure E
I
.extremity measure được sử dụng để thay đổi ngưỡng đưa vào so sánh với
GC khi lựa chọn mục tiêu ánh xạ .E
I
là local phase delta trong hình phần trước .
EXTREMITY MEASURE :
Procedure Compute_Extremity_measure
Input ts
I
,ah
I
,"iỴ N ,tỉ lệ a,b,
Output E
I ,

,
"
i
Ỵ
N ,-0.5 <= E
I
<=0.5
S1 tính toán biểu đồ của tất cả các node chú ý đến thời gian thực thi software(ts
I
) và không gian
hardware (ah
I
) .
S2 xác đònh ts(
a
), và ah(
b
) đáp ứng từ tỉ lệ
a
và
b
của t
s
và a
h
được chú ý trong biểu đồ .
S3 phân loại node vào tập software extremity node (EX
s
) và hardware extremity node (EX
h

)
chú ý :
If (ts
I
>=ts(
a
) and ah
I
<ah(
b
)) ,i
Ỵ
EX
s

If (ah
I
>= ah(
b
) and ts
I
<ts(
a
) ,i
Ỵ
EX
h

S4 xác đònh giá trò extremity x
I

cho node I :
If i
Ỵ
EX
s
then
Ts
i
/ts
max

,x
I
=
ah
i
/ah
max


else

ah
i
/ah
max

x
I
=

Ts
i
/ts
max


Trong đó :ts
max
=max
i
{
ts
i
}
và ah
max
=max
i
{
ah
i
}

S5 thứ tự những node trong EX
s
(EH
h
) cho bởi x .Trong đó giá tri extremity lớn nhất và giá trò
extremity nhỏ nhất là xs
max

(xh
max
) và xs
min
(xh
min
)
S6 tính toán extremity measure E
I
cho node I :
http:// www.diachiweb.com

If iỴ EX
s
then
x
I
-xs
min

E
I
= -0.5 * ,-0.5 <=E
I
<=0;
xs
max
-xs
min



else if iỴEX
h
then
x
I
-xh
min

E
I
= -0.5 * ,0<=E
I
<=0.5;
xh
max
-xh
min

Trong s1 tính toán phân phối những node chú ý đến thời gian thực thi software ts
I
và không
gian hardware ah
I
.thông số
a
và
b
đại diện cho tỉ lệ giới hạn của những phân phối nầy. Chẳng
hạn như trong S3 một node I được phân loại như là software extremity node , nếu nó vượt tỉ lệ a

trong biểu đồ ts (ts
I
>ts(
a
)) và dưới tỉ lệ
b
trong biểu đồ ah (ah
I
<ah(
b
)) .Tương tự một node I
được phân loại như hardware extremity nếu nó nằm trên tỉ lệ b trong biểu đồ ah (ah
I
>ah(b)) và
dưới tỉ lệ a trong biểu đồ ts (ts
I
<ts (a)). hình 5 sau trình bày các loại biểu đồ và nhận ra các
extremities .Ví dụ ta xem xét giá trò
a
và
b
nằm trong khoảng (0.5 ,0.75) được sử dụng .


















EX
h
EX
s








Số node trên ts



a
Cận trên
a







ts(
a
)

ts
Số node trên ah

b Cận trên b






ah(
b
) ah