The
Xo
Embedding:
An Embedding
o
Hype cubes
on o
Rings and To uses
An onio
Gondez
and
Miguel Vale o-Ga cia
Uni e si a Poli &cnica de Ca alunya
Depa amen
d'
A qui ec u a de Compu ado s
c/
G an
Capi an dn, Campus
Nod
-
Edi ici
D6
BO8071
Ba celona (Spain)
E-mail: (an onio,miguel} 9ac.upc.e~
Abs ac
Many pa allel algo i hms use hype cubes
as
he communica ion opology anwngp ocesses, which
make
hem sui able o be execu ed
on
a hype cube mul icompu e .
In
his way he communica ion
cos is kep
minimum
since p ocesses can
be
alloca ed o p ocesso s in such a way ha only
communica ion be ween neighbo p ocesso s is equi ed. Howe e , he scalabili y o hype cube
mul icompu e
is
cons ained
by
he ac ha he in e connec ion cos
pe
node
inc eases wi h he
o al numbe
o
nodes.
F om he poin o iew o scalabili y, meshes and o uses a e a mo e
in e es ing class
o
in e connec ion opologies.
In
his pape we p opose an embedding o
hype cubes
on o
omes
o
any gi en dimension, including one-dimensional omes which a e also
called ings. We
also
p o e ha his embedding
is
op imal in he sense ha i minimizes he
execu ion ime
on
a ing o a class o pa allel algo i hms equen ly
ound
in eal applica ions, such
as
FFT and
some
class o so ing algo i hms.
1.
In oduc ion
Many pa allel algo i hms use hype cubes
as
he
communica ion opology among p ocesses.
Some examples include pa allel algo i hms
o
FIT,
so s,
e c.
[Z].
We
will
call
hese
algo i hms
hype cube algo i hms
o
d-cube algo i hms.
whe e
d
is
he
numbe o dimensions
o
he hype cube.
A
hype cube algo i hm
o
dimension
d
o
d-cube algo i hm, consis s
o
2d
p ocesses
labeled om
0
o
9-1
such ha
e e y
p ocess communica es only wi h i s
d
neighbo s, one in
each
dimension
o
he d-cube.
In
his
pape we conside
he
p oblem
o
execu ing d-cube algo i hms on
mul icompu e s
[l
I.
A
mul icompu e is a dis ibu ed memo y mul ip ocesso in which
he
nodes
(p ocesso
+
local
memo y)
a e
in e connec ed h ough poin
o
poin
links.
The nodes
o
a mul icompu e
a e
in e connec ed acco ding
o
a gi en pa em
o
in e connec ion
opology.
I
his
opology is a hype cube
o
dimension
d
(d-cube mul icompu e ) hen
he
d-cube
algo i hm
can
be execu ed
on
he
mul icompu e in such
a
way ha neighbo
p ocesses
a e
mapped
on o
adjacen
nodes
(nodes di ec ly
connec ed
h ough a poin
o
poin link). We say, in
his
Case.
ha each
p ocess
o
he d-cube algo i hm
has
all i s
d
neighbo s a dis ance
I
in
he
mul icompu e
(i.e., all
equi ed
communica ion
is
be ween neighbo
nodes).
In
his
way, he cos
o
he
communica ion componen
o
he
d-cube algo i hm when i is execu ed on
a
hype cube
mul icompu e is kep minimum.
0-8186-3492-8193
$3.00
0
1993
IEEE
15
16
In e na ional
Con e ence
on Applica ion-Speci ic A ay
kesso s
An
impo an
d awback o hype cube
as
in e connec ion opology o mul lcompu en is
ha
i
is
no scalable.
In
a
dabe
mul icompu e
each
o
he
'
mdes
is
di ec ly
COM-
o
o he
d
nodes
h ough poin
o
poin links.
'Ihe e o e,
he.
cos
(and
he
complexi y) o
he
in e connec ion
ha dwa e
pe
node
inc eases wi h
he
numbex o
nodes.
0-
in e connec ion opologies, such
as
meshes
o
omes
a e
conside ed
mo e sui able o mul icompu e s wi h a la ge
numbe
o
nodes,
since
he
in e connec iOn cos
pe
node
does
no
depend
on
he
o al
numbe
o
nodes.
As
an
example,
each
node
o
il
wo-dimensional
o us
mul icompu e
is
di ec ly
co~ec ed
o
4
nodes.
i
does
no
ma e
he
numbe
o
nodes
o he mul icompu e .
When a dabe algo i hm is execu ed
on
a mul icompu e wi h a opology
o ie
han
hype cube
i is no possible, in
gene al.
o
alloca e
p ocesses
o
nodes
in such a way
ha
e e y
p ocess
has
i s
d
neighbo s
a
dis ance
1
in
he
mul icompu e .
As
an
example. in a wo-dimensional
om
mul icompu e . e e y
p ocess
has
a
mos
4
o
i s
d
neighbo s
a
dis ance
1.
I mus
ha e
a
leas
d-4
neighbo s
a
a dis ance g ea e
han
1.
A
message
o
any o
hese
" a " neighbo s mus
be
ou ed
h ough
he
poin
o
poin links
and
mdes
which
a e
ound along
he
pa h
o
he
des ina ion
node.
A
good
mapping o a d-cube algo i hm
on o
a mul icompu e will
y
o
keep
he
neighbo
p ocesses
as
close
as
possible in
he
mul icompu e , minimizing in
his
way
he
cos o he communica ion
componen o
he
d-cube algo i hm when i is execu ed
on
he
mul icompu e .
In
his
papex
we
p opose
an
embedding
o
d-cube algo i hms
on o
o us
mul icompu e s o any
a bi a y dimension.
This
embedding has
he
ollowing
p oees:
a) Fo
each
dimension o
he
d-cube, e e y
p ocess
has i s
co esponding
neighbo
a
he
same
dis ance (al hough
hese
dis ances
may
be
di e en
o
di e en dimensions).
b)
The
a e age dis ance
o
he
d
neighbo s
o
any
p ocess
is minimum, subjec
o
(a).
As
i will
be
shown
la e in
his
pape ,
p om
(a)
is
desi able
o
some kind
o
d-cube
algo i hms like
m,
since
i
gua an ees
ha
any p ocess will ne e ha e
o
wai o a neighbo
o
inish i s wo k be o e s a ing
he
in e change o
da a
wi h
i .
ROW
(b)
implies a minimum cos
in
he
communica ion componen o he d-cube algo i hm,
and
he e o e, a minimum execu ion
ime. We p esen a p oo
o
his
p ope y
o
ings
(onedimensional
o~~e~).
The
gene aliza ion
o
he p oo o
an
a bi a y dimension is s ill unde de elopmen
This
papa is
o ganized
as
ollows.
In
sec ion
2
we in oduce
some
no a ion
and
desc ibe
mo e
p ecisely
he
con ibu ion o
his
pape
as
well
as
some ela ed wo k.
Sec ions
3
p esen s he
p oposed
embedding o
dab
on o
ings.
In
sendion
4.
he
embedding is gene alized
o
omes
o
any a bi a y dimension.
In
sec ion
5
we p o e
ha
he
p oposed
embedding o ings is op imal
acco ding
o
he
c i e ion
in oduced in
sec ion
2.
Finally, we p esen
some
concluding ema ks.
2.
P elimina ies and ela ed
wo k
2.1.
De ini ions
A
d-cube
algo i hm
is
a pa allel algo i hm
ha
consis s o
2d
p ocesses
such ha e e y p ocess
communica es wi h exac ly
o he
d
p ocesses.
Tkse
d
p ocesses
a e
called i s neighbo s. We also
say
ha
he
communica ion opolo o
he
algo i hm is a hype cube. lha
means
ha he
2d
communica e) i
he
bina y
codes
o
n
and
m
di e in
a
single bi .
I
his
bi is
he
i- h bi hen
m
is
he
neighbo o
n
in dimemion i,
and
n
is
he
neighbo
o
m
in he same dimension
Then,
we w i e:
m
=
Ndn)
n
=
Ndm)
p ocesses
can
be
labeled om
0
o
Y
-1
in such a way ha p ocesses
n
andm
a e
neighbo (i.e.
hey
Session
2:
E icien
Design
Me hods
I
17
In
his
pape we ocus on d-cube
algo i hms
in which e e y
p ocess
has
he
ollowing s uc u e:
do
i=O,d-1
compu e
communica e wi h neighbo in dimension
i
enddo
In
his
algo i hm e e y
p ocess
consis s o d s ages,
each
o hem composed o a compu a ion
and
a communica ion
phase.
In
each s age, e e y
p ocess
uses
a
di e en dimension
o
exchange
in o ma ion wi h one o i s neighbo s.
We assume
ha
he du a ion o he compu e phase and he amoun o in o ma ion
o
be
exchanged is he same o all he
s ages
and all
he
p ocesses
o he d-cube algo i hm.
A
d-cube
algo i hm wi h he abo e ea u es will be called a compu e-and-communica e d-cube algo i hm,
o
a
CC
d-cube algo i hm o
sho .
'Ihis
kind
o d-cube algo i hms a e common in
eal
applica ions
like
FIT,
some
ype
o
so s,
e c.
Any pa allel algo i hm can be modelled
as
a g aph. The e ices o he g aph ep esen
he
p ocesses
o
he
algo i hm and he edges
o
he
g aph ep esen he neighbo ela ionship among
p ocesses.
A
mul icompu e can
also
be
modelled by a g aph.
The
e ices o he g aph ep eseni
he nodes
o
he mul icompu e
and
he edges o he g aph ep esen he poin
o
poin
links
which
in e connec hese nodes.
Mul icompu e s can
be
classi ied acco ding
o
hei
in e connec ion opology.
In
his
pape , we
a e in e es ed in mesh and
oms
mul icompu e s, since hey ha e scalable in e connec ion
opologies.
A
(kl,k2,
...,
kc)
c-dimensional
om
is an undi ec ed g aph in which
he
nodes
can
be labeled
as
c- uples (i1,iB
...,
ic),
0
ij
<
ki.
E e y node (i&
,....
ic)o
he
g aph has wo neighbo s in each
dimension o
he
oms.
I s
le neighbo in dimension
j
is (il
,...,($-
1)
mod
k,
...,
ic)
and
i s igh
neighbo in
his
dimension is (il,
...,
($+l)
mod
k,
...,
ic).
A
(k&,
...,
k,)
c-dimensional
mesh
is an undi ec ed g aph in which he nodes can
be
labeled
as
c- uples (i1.i~.
....
i,),
0
I
ij
e
kk
E e y node o
he
g aph has
wo
neighbo s in
each
dimension]
o
he mesh i
0
<
4
<
k,-1.
I s le neighbo is (il
....,
5-1
,...,
ic) and i s igh neighbo is (il,
...,
$+l
,...,
i,).
I
$=O.
he node
has
only a igh neighbo and i
$=k+
hen
i
only
has
a
le
neighbo .
A
line is a one-dimensional mesh while a one-dimensional o us is
called
a ing.
Figu e
1
shows some examples and illus a es how hei
nodes
a e labeled.
The dis ance in a g aph be ween wo e ices is he
minimum
numbe o edges ha join hose
e ices. In
he
pa icula case o he g aph which models a d-cube, he dis ance be ween
wo
e ices
is
known
as
he
Hamming dis ance (numbe o di e en bi s in hei bina y
ep esen a ions).
An
embedding o g aph
G
in o g aph
H
is a bijec i e unc ion
om he e ices o G
o
he
e ices o
H.
We assume
ha
G
and
H
ha e he same numbe o e ices.
The
p oblem o execu ing a
CC
d-cube algo i hm on a mul icompu e can
be
modelled
as
he
embedding
0-
g aph
G,
which ep esen s he
CC
d-cube algo i hm,
on o
g aph
H,
which ep esen s
he
mul icompu e .
The
dila ion o an edge
(n,m)
o
G
(edge joining e ices
n
and
m)
is he dis ance in
H
be ween
. W
andJ7m).
I
G
models a
CC
d-cube algo i hm, an edge
exis s
be ween e ices
n
and
m
i
m=Nin),
o
some
i
E
[O,d-I]. The dila ion o
his
edge will
be
deno ed by
Din).
Ob iously,
since
n=
Nim),
Din)
=
Dim).
When a
CC
d-cube algo i hm is execu ed on a mul icompu e ,
as
de ined by a gi en
18
In e na ional
Co& ence
on
Applica ion-Speci ic
A ay
heeo s
(4
(dl
d)
(4.4)
o us.The
pic un
also
show0
hoaw
ho
nod..
am
labeld.
Figu e
1:
Di e en
ypes
o
mul icompu e s:
a)
line,
b)
ing,
c)
(44)
mssh
and
embedding
;
a
communica ion be ween
p ocesses
n
and Nkn)
( equi ed
in i e a ion
i
o
he
CC
d-cube algo i hm)
is
implemen ed by
a
message which is ou ed h ough
Di(n)
poin
o
poin
links
and
D.W-1
nodes
o
he
mul icompu e ep esen ed by
H,
which
a e
ound in
he
sho es
pa h
be ween
nodes ln)
and lNkn)).
We
deno e
by
To
he du a ion o he a i hme ic compu a ion phase in e e y s age o
he
CC
d-cube algo i hm, when i is execu ed
on
he a ge mul icompu e . We deno e by
Tc
he cos o
sending
a
message
h ough
a
poin
o
poin
link
on
he
mul icompu e .
The ime
o
execu e
a
CC
d-cube algo i hm
on
a
mul icompu e wi h
9
nodes,
as
de ined by
embedding can
be
exp essed
as:
T
=
dTa
+
Tc
whe e
Tc is
he
cos o he communica ion componen o
he
CC
d-cube algo i hm.
Tc
can be
exp kgsed
as
ollows:
Tg
=
nuu
(Td-I(n):
n=0..2%)
Tiin) =D,in) Tc
+
nuu
(Ti-dn),
Ti.l(Nkn))
I
i"&)
=
0
(a)
(b)
In
he abo e exp essions,
Tin)
is he cos o he communica ion componen o
p ocess
n
&om
he beginning o he execu ion o he end o s age
i.
Exp ession
(a)
indica es
ha
Tgis
equal o he
highes communica ion componen
cos
o any
p ocess
a
he
end
o
he
d
s ages
o
he
CC
d-cube
algo i hm. Exp ession
(b)
gi es
he
communica ion
componen cos o
p ocess
n
a
he
end o s age
i.
In
his
s age
p ocess
n
mus exchange in o ma ion wi h i s
neighbo
Nin).
?he
cos
o exchanging
his
in o ma ion
is
Di(n)T,
Howe e ,
his
exchange
caauo
s a
un il
bo h
p ocaws
n
and
Ni(n)
a e
eady
o
do
i .
In
gene al, ei he
p ocess
n
o
p ocess
Ndn) will ha e
o
wai o
i s
neighbo
o
a i e o
he
poin in which communica ion can be
s a ed.
lMs
is
why
he
e m
"max"
appea s
in
expsion (b).
In
he ollowing, we
call
hose
idle
pe iods
as
wai ing
pe iods.
Ob iously, i he mul icompu e
has
a
d-cube
in e coIlnec ion
opology
hen
he bes embedding
is ln)
=
n
(iden i y
embedding).
In
his
case
Din)
=
I
( o e e y
i
and
n)
and he execu ion ime
is
T,
=
d(Ta+T,)
Session
2
E icien Design Me&&
I
19
2.2.
Con ibu ions
In
his
pape . we a e in e es ed in hose
embeddings
in which
Dkn)
=
Di
(i
E
[O,d-I]
and
n
E
[O,2d-I]).
This
means ha e e y
p ocess
has i s
neighbo
in dimension
i
a
he
same dis ance in
@e
a ge mul icompu e .
In
he
ollowing,
an
embedding
wi h
his
ea u e
is
called
embedding
wi h
cons un
dis ances
and
he
alues o
Di
(i
E
[O,d-I])
a e
called
he
dis unces
o he embedding.
Embeddings wi h cons an dis ances ha e
he
p ope y
ha e eay
p ocess
akes
he
same ime
o
communica e
in
any gi en s age o he
CC
d-cube algo i hm.
Because
he
du a ion o he compu e
phase
is
also
he
same
o
e e y
p ocess,
wai ing pe iods
a e
a oided since
neighbo
p ocesses
a i e
a
he
same ime
o
he poin a which hey ha e
o
communica e.
The
ime
o
execu e a
CC
d-cube algo i hm
on o
a mul icompu e .
as
de ined
by
an
embedding
wi h cons an dis ances
is:
d-
1
d-
1
T,
=
x
(Ta+DiTc)
=
dTa+TcxDi
=
d(T,+TcDa)
i=O
i=O
whe e
Dais
he
a e age dis ance
o
he
embedding:
d-
1
XDi
=
a e agedis ance
( ~
0,
-
i=O
d
The e o e.
he
embedding wi h
cons an
dis ances which
minimizes
T is
ha
whose a e age
dis ance
D,
is minimum.
An
embedding wi h such
p ope y
is
said
o
be
op imal.
As
i was men ioned in
he
in oduc ion, we
a e
in e es ed in execu ing
CC
d-cube algo i hms
on
scalable mul icompu e s.
In
pa icula . we a e in e es ed in
om
mul icompu e s
since
o meshes
a well-known embedding. desc ibed in
he
nex
sec ion,
is op imal o
CC
d-cube algo i hms.
In
his
pape
we p opose
an
embedding wi h cons an dis ances o
CC
d-cube algo i hms on o
om
mul icompu e s o any a bi a y dimension. Mo eo e , we p o e ha
he
p oposed
embedding wi h
cons an
dis ances
is op imal
o
ings (onedimensional
ow).
Ano he
addi ional
p ope y
o he
p oposed
embedding is i s simplici y, which means a negligible cos
o
compu e
he
loca ion o any
p ocess
in he mul icompu e .
2.3.
Rela edwo k
The
p oblem o embedding d-cubes on o meshes
and
o uses
has
been
p e iously conside ed
by
o hex
au ho s.
We
mw e iew some ela ed wo k.
Ma ic
p esen s
in
[7]
a s udy o
he
s anda d
embedding
(de ined below) o d-cubes
on o
wo-dimensional meshes and
o uses.
To
de ine
he
s anda d
embedding
(which will be deno ed by
$
o a d-cube
on o
a
line
o
a
ing.
he
nodes
o
he
a ge mul icompu e
a e
numbe ed om
0
o
-I
(see
igu es 1.a
and
1.b).
Then,
he
s anda d
embedding is
de ined
by
(see
igu e 2.a):
,,d(n)
=
?I
n e
s anda d
embedding o a d-cube
on o
a
(kl,k
=....kc)
cdimensional mesh
o
om
is de ined
as
ollows:
s,d(")
=
(PI*P ,
...,Pc)

20
In e na ional Con e ence on Applica ion-Speci ic A ay
P ocesso s
0123
e------*
12 13 14
01 234561
(a)
(b)
Figu e
2:
S anda d embeddings
o :
a)
a
3-c-
on o
a
line
o
a
ing
and
b)
a
kube on o
a
(4,4)
mesh
o o us.
Each
label indka es
whkh
e ex
o
he
dcube is mapped on o
each
node
o
he
mul icompu e .
W apa ound links
a e
no
shown
o
cla i y.
whe e:
i-
1
p,
=
(n
mod ikj)di nkj
Figu e 2.b shows an example in which
c=2
and
kl=k2=4.
Ob iousl
he
s anda d embedding is
a
cons an dis ance embedding. Fo he pa icula
case
in which
ki=g‘,
i
E[~,c].
he
dis ances o
he s anda d embedding
a e:
j=1
j=l
Q
=
2
i
ie[O,
d
-
I]
I can
be
shown
ha
he
s anda d
embedding is
op lmal
o
meshes.
in
he
sense
ha
i
minimizes
he a e age dis ance [3],[8]. Howe e , i is no op imal o
o uses,
as
i will be shown
la e
in
his
Pape .
Ha pe
in [41 and
Lai
and Spague in [5] sol e he p oblem o embedding d-cubes on o meshes
o
minimize
he dila ion o
he
embedding ( he maximum dila ion o any edge). Bo h
p oposals
use
he
byweigh
embedding, deno ed by h, which is no an embedding wi h cons an dis ances. Nex ,
we desc ibe b ie ly
his
embedding.
In
he
case o a line, he labels o he e ices which ep esen he
p ocesses
o he d-cube
algo i hm a e o de ed by hei weigh s.
The
weigh o a label is
he
numbe o
I’s
in
i s bina y
ep esen a ion. Labels wi h
he
same weigh
a e
o de ed
in
descending
o de .
Then,
he
p ocesses
o he d-cube o de ed in ha way a e alloca ed
o
he
nodes
o
he
line,
om
le
o
igh . Figu e 3.a
shows an example. The byweigh embedding can
be
ex ended
o
meshes o any dimension. In
pa icula , Lai and Spague ex end
his
embedding
o
wo-dimensional meshes
in
[5]. Figu e 3.b
shows an example.
The byweigh embedding
minimizes
he dila ion o
he
embedding.
?his
is
an
in e es ing
p ope y
in
some pa icula applica ions o embeddings. Fo ins ance,
Lai
and Spague p opose
his
embedding
o
sol e he p oblem o placing
he
p ocesso s o a hype cube on a p in ed ci cui boa d
o
a chip (which
can
be
modelled
as
a
wo-dimensional mesh). Howe e , he byweigh embedding
is no an embedding wi h cons an dis ances, which is an impo an p ope y
in
he con ex o
execu ing
CC
d-cube algo i hms on o mul icompu e s. ’Ihe e o e, du ing he execu ion o
he
CC
d-cube algo i hm, wai ing
pe iods
will
appu
which con ibu e
o
inc ease
he
execu ion
ime.
To
illus a e
his
ac , igu e4 shows an example in which
he
execu ion imes o a
CC
3-cube algo i hm
Session
2:
E icien
Design
Me hods
I
21
OOO
100
010
001
110
101
011
111
(a)
Figu e
3
Byweigh embeddings
o :
a)
a
3-cube
on o
a
line and b)
a
Scube
on o
a
(8,4)
mesh.
on a line
o
bo h he s anda d embedding
and
he byweigh embedding
a e
compa ed. The wai ing
pe iods
which con ibu e o
make
he byweigh embedding un slowe
han
he
s anda d embedding
a e also
shown.
In
[6],
Y
.W. Ma and
L.
Tao
p oposed se e al embeddings among
o uses
and
meshes
o di e en
dimensions.
Thei
p oposals
a e
based on gene alizing he
concep s
o g ay code o adix-2
numbe ing sys em o mix- adix numbe ing sys ems. Since a d-cube
can
also
be
seen
as
a
d-dimensional mesh
o
o us wi h wo elemen s in
each
dimension.
lki
embedding can also be
applied o sol e he p oblem add essed in
his
pape . Howe e , hey ocus on minimizing he
dila ion
( he
la ges dis ance be ween
any
wo
neighbo s o
he
d-cube) and he e o e he esul ing
embeddings in gene al do no ha e cons an dis ances, which
is
a desi able p ope y
o
ou
objec i e. Howe e , i one
s a s
wi h a d-cube ep esen ed by means
o
a (2.2,
...
2)
d-dimensional
mesh
o
o us, hen
he
esul ing embedding on o a ing
o
a wo-dimensional o us has cons an
dis ances. Ne e heless, i s a e age dis ance and he e o e i s
pex onnance
o execu ing ou a ge
algo i hm is wo se han
he
embedding p oposed in
his
pape .
3.
We desc ibe now he
p oposed
embedding wi h cons an dis ances o a d-cube on o a ing wi h
Zd
e ices (we assumed
>
I).
We call
his
embedding
xo
embedding
and i is deno ed
by ,,
The
xo embedding is op imal, in he sense ha i
minimizes
he
a e age
dis ance.
The xo embedding
is desc ibed nex . Sec ion
5
p esen s a p oo
o
i s op imali y.
Le
G
be
he g aph which ep esen s he
CC
d-cube algo i hm and
R
be he g aph which
e esen s he ing mul icompu e . Assume ha
he
e ices o
R
a e labeled om
0
o
2
-1clockwise
(see
igu e 1.b). Le
(nd-1, nd.2
...,nl,
no)
be
he
label
(in
bina y
code)
o e ex
n
in
G.
This
e ex is mapped on o e ex
m= ,,(n)
in
R,
whose label in bina y
code
(md+..,ma)
is:
An
embedding
wi h
cons an dis ances
o
ings
F
mi
=
ni
i
E
[O,
d-11,
i
#
d-2
md.2
=
XOR
(nd.19 nd.3
whe e
XOR
(qb)
is he exclusi e-o
o
bi s
a
and
b.
Figu e
5
shows an example
o
d=4.
The dis ances
o
he xo embedding a e:
Di
=
2'
i
E
[O,
d-21
Dd-1
=
2d-2
22
In e na ional Con e ence on Applica ion-Speci ic A ay
P ocesso s
124 332
124 422
124 431
124 431
124 422
124 332
124 321
Compu a ion
Communica ion
Wai ingpe iod
bw
(b)
(C)
Figu e
4
a) Dila ions
o
he s anda d and byweigh embeddings
(M).
Execu ing
a
CC
3-cube algo i hm on a line using: b) he s anda d
embudding
and
c) he byweigh embedding.
me e o e,
he
a e age
dis ance
is:
d-2
4.
An embedding
wi h
cons an dis ances
o
c-dimensional
o uses
Now we desc ibe
he
xo
embedding o a d-dimensional hype cube on o a
(2d',2d2,...,2d3
c-dimensional
o us
such ha
dl+d2+
...+
d,=d.
Gi en a posi i e in ege
x,
le
diJ
deno e
he
i h
bi o he bina y ep esen a ion o
x.
The
leas
signi ican bi is conside ed o
be
he
0 h
bi . We
also
de ine Kjin
he
ollowing way.
K1=0,
and
o
e e y
I<jG+l
we ha e ha :
j-
1
Kj
=
di
i=
1
Session
2:
E icien Design Me hods
I
0
1
2
3
4
5
6
7
121314
15
8
9
10
11
11111111111
-
23
Figu e
5:
A
xo
embedding
o
a
4-cube
on o a ing.
The
labels
indica e which
node
o
he dcube
is
mapped
on o he co esponding node
o
he ing.
Le
G
be
he
g aph which ep esen s
he
d-cube and
T
be he g aph which ep esen s he o us.
men, e ex
n
o
G
is mapped on o e ex
(mpa
...,mc)= m
in)
in
T
as
ollows:
mJ{i)
=
n(i+Kj)
mJ{dj
-
2)
=
XOR
(n(Kj+l-
I),
n(Kj+,
-
2))
i
E
10,
dj
-
I],
i
dj
-
2
Fo
he
pa icula
case
o a (2dc,
...,
99
c-dimensional o us,
he
dis ances co esponding o
his
embedding a e:
Di
=
zd/c-2
D.
=
$m~ddc
o he wise
i
i
=
1
(ac)
-
I,
0
e
1
5
c
and he a e age dis ance
is:
d/c-2
.
2dIC-2
[
-k
=O
2’)
- -
c(2d/c-2+2d/c-1-
1)
d d
D,
=
Figu e
6
shows an example o
d=6.
No e
he
simplici y o unc ion ’Jn).
?his
unc ion, which
is used e y equen ly o ou ing messages du ing he execu ion o
he
CC
d-cube algo i hm,
consis s
o simple bi ope a ions
and
i s compu a ional cos is negligible.
5.
P oo
o
op imali y
o ,,,
o
ings
Ou
c i e ion
o
measu e he goodness o any embedding wi h cons an dis ances is i s a e age
dis ance
as
de ined in sec ion 2, since minimizing he a e age dis ance implies minimizing he
execu ion ime
o
CC
d-cube algo i hms. In
his
sec ion we p o e ha he xo embedding has he
minimum a e age dis ance o emwngs wi h cons an dis ances o hype cubes
on o
ings.
To
show ha he xo embedding is op imal o ings, we will p o e ha he a e age dis ance
o
any embedding wi h cons an dis ances is highe han o
equal
o
he a e age dis ance o heh,
embedding.
This
is
s a ed
by heo em
10.
Be o e
his
heo em we p esen se e al lemmas and
co olla ies
ha
a e needed
o
p o e
ha
esul Fi s we ind a lowe bound o he sum o any
se
o
d-ldis ances
co esponding
o
any
embedding wi h cons an dis ances. men, we
ind
a lowe
bound o he highes dis ance o he embedding. Bo h oge he gi e a lowe bound o he a e age
dis ance o any embedding wi h cons an
dis ances.
This
lowe bound is
he
a e age dis ance o he
m
embedding, which p o es i s op imali y.
De ini ion:
Gi en any node o a hype cube, we de ine
Ndn).
whe e
D
is any subse o
dimensions o he hype cube,
as
he
node
ha we each i we
s a
a node
n
and we mo e h ough
e e y dimension in
D,
one a e
ano he ,
using each dimension exac ly once
(as
we know, he o de
in which
he
dimensions
a e
used
does
no ma e ,
he
esul will be
he
same).
Fo
ins ance,
i
D=[l,3),
hen
Ndn)
=
N3(Nl(n))
=
NI(N3(n)).