A Study of Online Task Placement for Dynamic Partial Reconfigurable Devices
概要
5?9-.-.G2,78'()*=@>
( @A0 E ;2 % : 85: 1 ) - ?7 & 8- /19 1: @
2 ;> E: - 9 5/ & - >@5- 8
' 1/;: 2 53 A>- . 81 1B5/1?
;
E
A
) 5: 3 EA , % *
2,78'()*0./3
4D=6 B+DC=@
, *,* 1 +, 6
( 5: / 1
@4 1
?
1 : 1 >- 8 & A><;?1
- ? 1 : @>- 8 & >;/ 1 ??5: 3
! ? 4- B1
. 1 / ;9 1
/ ;9
- . 585@E
@; - / 4 51 B 1
- >1 : ;@ 0 1 ?53 : 1 0
@59 1
* : 5@? & * ?
- ? - :
@4 1
0 1 B 5/ 1 ?
. - ?5/
-: E
9 - @>5D
/ ;9 <81 D
2 ;> 9 1 1 @5: 3
;<1 >- @5;: ?
B - >51 @E
2 81 D 5. 585@E
0 - @-
!
1 @/
@;
2 A88E
- / 4 51 B 1
;2
@4 1
& & ?
2 - ?@ >1 - 8
<>;/ 1 ??5: 3
59 - 3 1
) ;
4- B1
;C 1 B 1 >
@4 1 >1 = A5>1 9 1 : @ ;2
/ ;9 <81 D
/ ;9
-
;<1 >- @5;: ?
8- >3 1 ?/ - 81
>@52 5/ 5- 8 ! : @1 8853 1 : / 1
?<1 / 5- 85F1 0
4 53 4
?A/ 4
59 <;>@- : @ <- >@ ;2
/ ;9 <;: 1 : @? ;2
& & ? C 5@4
- <<85/ - @5;: ? ;>
8- >3 1
& >;/ 1 ??;>? & & ?
?A/ 4
-?
<>;/ 1 ??5: 3
-: 0
- / / 1 81 >- @1
?A/ 4
4 53 4 1 >
<1 >2 ;>9 - : / 1
?<1 / 5- 8 <;?1 ! ? ?A/ 4 - ? <<85/ - @5;: ( <1 / 52 5/ ! ? ( ! ?
>- <4 5/ ?
& >;/ 1 ??5: 3
* : 5@?
& * ?
-: 0
53 5@- 8
( 53 : - 8
& >;/ 1 ??;>? ( & ?
1 @/
- >1 0 1 ?53 : 1 0 C 4 581 ?A/ 4 ! ? 8;?1 ?53 : 52 5/ - : @
<;>@5;:
;2
2 81 D 5. 585@E
3 >- : @1 0
1 D / 4 - : 3 1 2 ;> <1 >2 ;>9 - : / 1 3 - 5: ?
% : / 1 - :
.E
( !
& & ?
5:
;> - ?<1 / 5- 8
<;?1 <>;/ 1 ??;> 5? 9 - : A2 - / @A >1 0 5@? 2 A: / @5;: - 85@E C 588 . 1
: ;@ - . 81 @; . 1 / 4 - : 3 1 0
) 41
1 9 1 >3 1 : / 1
;2
>1 / ;: 2 53 A>- . 81
& >;3 >- 9 9 - . 81 - @1 >>- E ? & ?
@; . - 8- : / 1 @4 1 / ;9
!:
3 1 : 1 >- 8
- >>- E
;2
@4 1
<>;3 >- 9 9 - . 81
;2
>1 = A5>1 9 1 : @? . E
<>;3 >- 9 9 - . 81
@;
.1
0 1 B 5/ 1
5? / ;9 <>5?1 0
C 4 5/ 4
1 : @5>1 8E
;>
<- >@5- 88E
;2
1 : - . 81 ?
0 52 2 1 >1 : @ 2 A : / @5;: ? . - ?1 0
;:
@4 1
/ A ?@;9 1 >?
>1 / ;: 2 53 A>5: 3
?<1 / 5- 88E
-:
0 E : - 9 5/
@4 ;?1
<- >@5- 8
& '
?/ 4 1 9 1 1 : - . 81 ? <- >@ ;2 0 1 B 5/ 1 / 5>/ A5@?
>1 / ;: 2 53 A>1 0
1 D 1 / A @5;:
<>;B 50 1 ? - 3 ;;0 9 1 @4 ;0
>1 ?;A>/ 1 ?
/ 5>/ A5@?
>1 / ;: 2 53 A>- @5;:
51 80
<1 >2 ;>9 - : / 1 - : 0 2 81 D 5. 585@E ;2 ! ?
>1 / ;: 2 53 A>- . 81
59 <81 9 1 : @- @5;:
0 1 B 5/ 1 ? 5: / 8A 0 5: 3
;2
-@
;@4 1 >
>A : @59 1
<- >@?
?;
C 5@4 ;A@
@4 - @
@4 1
0 5?@A>. 5: 3
@4 1
2 81 D 5. 585@E
-: 0
<1 >2 ;>9 - : / 1 ;2 @4 1 >1 / ;: 2 53 A>- . 81 0 1 B 5/ 1 - >1 2 A88E 59 <>;B 1 0
) 41
>1 / ;: 2 53 A>- . 81
& & ? -: 0
0 1 B 5/ 1
5: @1 : 0 ? @; 2 588 @4 1
?<1 / 5- 8 <;?1
! ?
9 A/ 4 4 53 4 1 > <1 >2 ;>9 - : / 1 @4 - :
81 B 1 8 ;2 2 81 D 5. 585@E @4 - :
;C 1 B 1 >
+ 41 :
5:
-:
@4 1 >1 - >1
- <<85/ - @5;:
/ ;;<1 >- @5;:
@4 1
@- ?7?
) 41:
?; - ? @; - / 4 51 B 1 <;@1 : @5- 88E
& & ? -: 0
9 - 5: @- 5:
-
4 53 4 1 >
@4 - @ ;2 ?<1 / 5- 8 <;?1 ! ?
?@588 <>;. 81 9 ? @4 - @ : 1 1 0
- @@1 9 <@? @; . 1 1 D 1 / A @1 0 ;:
C 5@4 - & '
- <<85/ - @5;:
3 - < . 1 @C 1 1 :
/ ;: @>;8 ?E ?@1 9
5? 2 5>?@8E
0 5B 50 1 0
1 - / 4 @- ?7 5? <8- / 1 0
;:
5: @;
5:
@; . 1
- & '
?;8B 1 0
0 1 B 5/ 1
- 9 5/ >;<>;/ 1 ??;>
B - >5;A ? 4 - >0 C - >1
@4 1 & '
0 1 B 5/ 1 - ? @4 1
. - ?5/ 1 D 1 / A@5;:
>1 9 ;B 1 0 2 >;9
A: 5@ - : 0 1 D 1 / A @1 0
A>@4 1 >9 ;>1 @4 1 @- ?7 5?
@4 1 0 1 B 5/ 1 ;: / 1 5@ 1 : 0 ? 1 D 1 / A @5;:
?; @4 - @ @4 1
<>;3 >- 9 9 - . 81 >1 ?;A>/ 1 ? ;/ / A <51 0 . E @4 1 @- ?7 / - :
- : 0 >1 A ?1 0 . E ;@4 1 > @- ?7?
* : 0 1 > @4 1 & '
?/ 4 1 9 1 @4 1 @- ?7
<8- / 1 9 1 : @ - : 0 >1 9 ;B - 8 <>;/ 1 ??1 ? 4 - B 1 . 1 1 :
@59 1
?; @4 - @ @4 1
>1 ?;A>/ 1
;: 3 ;5: 3
?@- @A ? 5? / 4 - : 3 1 0
) 4 1 >1 2 ;>1 @4 1 - 0 B - : @- 3 1 ;2
@4 1 & '
. 1 >1 81 - ?1 0
- @ >A:
-@ -: E
@59 1
0 1 B 5/ 1 / ;9 1 ? C 5@4 @C ;
/ >5@5/ - 8 5??A 1 ? @; . 1 ?;8B 1 0
@- ?7 <8- / 1 9 1 : @ 0 1 / 50 1 C 4 1 >1
@; <8- / 1 1 - / 4 4 - >0 C - >1 @- ?7 @; 1 : ?A>1 @4 1 9 - D 59 A9
859 5@1 0
<>;3 >- 9 9 - . 81
<>1 / 5?1 8E
>1 / ;>0
>1 ?;A>/ 1 ? ;:
-: 0
>1 ?;A>/ 1 ?
A <0 - @1
@4 1 & '
@4 1
>1 ?;A>/ 1
9 - : - 3 19 1: @
?@- @A? ;2
<>;3 >- 9 9 - . 81
0 1 B 5/ 1 1 2 2 5/ 51 : @8E
) - ?7 <8- / 1 9 1 : @ - : 0
>1 ?;A>/ 1 9 - : - 3 1 9 1 : @ <>;. 81 9 ? <8- E - :
- <<85/ - @5;:
0 5>1 / @8E
A ?1 ;2
1 D 1 / A @5;:
59 <;>@- : @ >;81 5:
@4 1
<>;/ 1 ?? - ? @4 1 @- ?7 <8- / 1 9 1 : @ <;?5@5;:
- 2 2 1 / @? @4 1
A ?- 3 1
>- @1
;2
859 5@1 0
<>;3 >- 9 9 - . 81
>1 ?;A>/ 1 ?
1 ?50 1 ? @; 2 A>@4 1 > 59 <>;B 1 @4 1 <1 >2 ;>9 - : / 1 ;2 & '
9 ;>1
1 D <8;>- @5;: ? ;:
/ - >>51 0
;A@
;>
@4 1
5: @1 3 >- @5;:
2 A@A>1
>1 / ;: 2 53 A>- . 81
/ ;9 <- >1 0 C 5@4 @4 1
<>;3 >- 9 9 - . 81
0 1 B 5/ 1
4- B1
0 A1
@;
-: 0
0 1 B 5/ 1
% :
. 11:
- >/ 4 5@1 / @A>1 ?
0 1 B 5/ 1 ?
?4 ;>@1 > C 5>1 81 : 3 @4
2 ;> 4 1 @1 >;3 1 : 1 ;A? & '
- >>- : 3 1 0
- >/ 4 5@1 / @A>1
0 1 B 1 8;<9 1 : @ @>1 : 0
0 1 : ?5@E
/ ;: ?A9 <@5;:
0 1 B 5/ 1
4 ;9 ;3 1 : 1 ;A ? & '
@4 >1 1 0 59 1 : ?5;: - 8
. 1 / ;9 1
@4 1
0 1 B 5/ 1 ?
3 >- 0 A- 88E
@4 1
4 53 4 1 >
8;C 1 > 1 : 1 >3 E
@4 1 ;@4 1 > 4 - : 0
0 1 B 5/ 1 - >/ 4 5@1 / @A>1 ? 0 52 2 1 >1 : @ ?4 - <1 0
>1 ?;A>/ 1 ? ?A/ 4 - ? "
' #
@; 59 <81 9 1 : @ B - >5;A ? 2 A: / @5;: ?
1 2 2 5/ 51 : @ - 83 ;>5@4 9 ? - >1 1 D <1 / @1 0
-: 0
( &
) 4 1 >1 2 ;>1
@; 4 - : 0 81
- >1
4 53 4 8E
@- ?7 <8- / 1 9 1 : @
- : 0 >1 ?;A>/ 1 9 - : - 3 1 9 1 : @ 5??A 1 ? 2 ;> 1 - / 4 0 1 B 5/ 1 - >/ 4 5@1 / @A>1
!:
@4 5?
- 83 ;>5@4 9
@4 1 ?5?
2 ;>
?@>A/ @A>1
: -9 10
2 5>?@8E
& '
-
2 - ?@
# - D 59 - 8
2 ;> 1 D 1 / A@5: 3
9 <@E
- 83 ;>5@4 9
1 2 2 5/ 51 : @ 0 - @ #
85?@
5?
0 1 B 5/ 1 ? @; 2 5: 0 - <>;<1 >
- @- ?7
+ 4 1 :
- @- ?7 C 588 . 1 - ??53 : 1 0
1 D 1 / A @1 @4 1 @- ?7 . E ?1 - >/ 4 5: 3
;> >1 9 ;B 1 0
9 - : - 3 1 0 . E A <0 - @5: 3
A. ;50
<8- / 1 9 1 : @
- : 0 1 D 1 / A@1 0 <>;<1 > 8;/ - @5;: ? ;:
@- ?7 5? - ??53 : 1 0
@- ?7
0 1 B 5/ 1 ? 5? <>;<;?1 0
:
<>;<;?1 0 @; 9 - : - 3 1 2 >1 1 ?<- / 1 ;:
8;/ - @5;:
;: 85: 1
@4 1 0 1 B 5/ 1 / - :
@4 1 #
85?@
<>;3 >- 9 - . 81
. 1 2 ;A : 0 @;
$ ; 9 - @@1 > @4 1
>1 ?;A>/ 1 ? / - :
.1
@4 1 85?@
) 4 1 1 2 2 5/ 51 : / E ;2 @4 1 <>;<;?1 0
5? @4 1 ;>1 @5/ - 88E
B 1 >52 51 0
-: 0
?59 A8- @5;:
>1 ?A 8@?
?4 ;C @4 1 4 53 4 1 > 1 2 2 5/ 51 : / E / ;9 <- >1 0 C 5@4 1 D 5?@5: 3
( 1 / ;: 0 8E
@;
9 - : - 3 19 1: @
- 0 0 >1 ??
@4 1
@- ?7
<>;. 81 9 ?
2 ;>
9 A 8@5 ?4 - <1 0
4 1 @1 >;3 1 : 1 ;A ?
<>;<;?1 0
@;
- <<851 0
& '
0 1 B 5/ 1
9 ;0 1 8 @4 1
@; 9 - : - 3 1
-
@- ?7
<8- / 1 9 1 : @
-:
-: 0
>1 ?;A>/ 1
@- ?7?
/ ;: @5: A;A?
-: 0
- 83 ;>5@4 9 ?
;:
. 8;/ 7
-
85?@
5?
5: @1 >B - 8 85?@ ?1 @ 5?
4 1 @1 >;3 1 : 1 ;A ? <>;3 >- 9 9 - . 81
>1 ?;A>/ 1 ?
) 4 1 <>;<;?1 0 9 1 @4 ;0 5? @4 1 ;>1 @5/ - 88E - : - 8E F1 0 - : 0 1 B - 8A- @1 0
. E ?59 A8- @5;:
? -
>1 ?A 8@
9 1 @4 ;0 5? 1 D / 1 881 : @ 5:
) 4 1 0 5??1 >@- @5;:
!:
@4 1
2 1 - @A>1 ? ;2
@4 1 & '
;:
-:
0 1 B 5/ 1
& '
- >/ 4 5@1 / @A>1
-: 0
@4 1
) 4 1 / ;: @>5. A @5;:
5? - 8?; 1 D <8- 5: 1 0
;B 1 >B 51 C
;2
@- ?7 <8- / 1 9 1 : @ - : 0
@4 1
;2 @4 5? >1 ?1 - >/ 4 5? 5: @>;0 A/ 1 0
?/ 4 1 9 1 - >1 0 1 ?/ >5. 1 0
;2 @4 5? 0 5??1 >@- @5;:
?E ?@1 9
<>;<;?1 0
5? ;>3 - : 5F1 0 - ? 2 ;88;C ?
>1 / ;: 2 53 A>- . 81
4 - <@1 >
@4 - @ @4 1
<8- / 1 9 1 : @ = A- 85@E - : 0 <1 >2 ;>9 - : / 1
4 - <@1 > @4 1 9 ;@5B - @5;:
) 41:
!:
5@ 5? ?4 ;C :
0 1 B 5/ 1
- >1
@4 1
>1 / ;: 2 53 A>- . 81
>1 ?;A>/ 1
/ ;9
9 - : - 3 1 9 1 : @ <>;. 81 9 ?
0 1 ?/ >5. 1 0
: 0
1 D 5?@5: 3
@- ?7
<8- / 1 9 1 : @ @1 / 4 : ;8;3 51 ? - >1 0 5?/ A??1 0 - : 0 - : - 8E F1 0
!:
4 - <@1 >
-:
4 ;9 ;3 1 : 1 ;A ? & '
. - ?1 0
;:
-
?4 ;C
@4 - @
>1 61 / @5;:
;: 85: 1 @- ?7 <8- / 1 9 1 : @ - 83 ;>5@4 9
0 1 B 5/ 1 - >/ 4 5@1 / @A>1 ? 5? <>;<;?1 0 C 4 5/ 4 5?
: ;B 1 8 0 - @@4 1
2 ;>
?@>A/ @A>1 #
<>;<;?1 0
- 83 ;>5@4 9
>- @5; . E - @ 81 - ?@
D <1 >59 1 : @- 8 >1 ?A8@?
/- :
>1 0 A/ 1
@4 1
@- ?7
/ ;9 <- >1 0 C 5@4 @4 1 @>- 0 5@5;: - 8
9 1 @4 ;0 ?
!:
4 - <@1 > 2 ;>
-:
5: @1 >B - 8 85?@ ?1 @ 5? 2 5>?@8E 5: @>;0 A/ 1 0 @; 9 - : - 3 1 - B - 58- . 81
<>;3 >- 9 9 - . 81
- 83 ;>5@4 9
4 1 @1 >;3 1 : ;A? & '
>1 ?;A>/ 1 ?
/ ;9 . 5: 1 0
-: 0
C 5@4
-:
-
0 1 B 5/ 1 - >/ 4 5@1 / @A>1 ?
5: @1 >B - 8 . - ?1 0
<8- / 1 9 1 : @
8;C 2 >- 3 9 1 : @- @5;:
?1 81 / @5;:
?@>- @1 3 E 5? <>;<;?1 0 @; ?;8B 1 @4 1 <8- / 1 9 1 : @ <>;. 81 9
?4 - <1 0
@- ?7?
) 41
<>;B 1 0
@4 1 ;>1 @5/ - 88E
@4 - @ @4 1 >1 61 / @5;:
- B 1 >- 3 1
1 2 2 5/ 51 : / E
-: 0
;2
@4 1
?59 A8- @5;:
<>;<;?1 0
9 1 @4 ;0
>1 0 A/ @5;:
;2
5?
>1 ?A8@? 0 1 9 ;: ?@>- @1
>- @5; 5? 0 1 / >1 - ?1 0 . E - @ 81 - ?@
2 >- 3 9 1 : @- @5;:
;2 9 A 8@5
C 5@4 - :
/ ;9 <- >1 0
C 5@4
@>- 0 5@5;: - 8 9 1 @4 ;0 ?
5: - 88E 4 - <@1 >
) ; ?A 9
?A9 9 - >5F1 ? - : 0 - 0 0 >1 ??1 ? 2 A @A>1 C ;>7?
A < @4 5? 0 5??1 >@- @5;:
<8- / 1 9 1 : @
- 83 ;>5@4 9 ?
4 1 @1 >;3 1 : 1 ;A ? & '
<>;<;?1 0 1 2 2 5/ 51 : @ ;: 85: 1 @- ?7
2 ;>
0 1 B 5/ 1 ? . - ?1 0 ;:
4 ;9 ;3 1 : 1 ;A ?
-: 0
: ;B 1 8 0 - @- ?@>A/ @A>1 ?