Transcript Convertibility Verification and Converter Synthesis: Two Faces of the

Depth-Bounded Communication
Complexity for Distributed
Computation
Student: Jie-Hong Jiang
Mentor: Prof. Robert Brayton
EE249 Class Project
12/3/2002
Motivation

In system-on-chip design, computation tasks
may be localized in some particular locations
(e.g. analog/digital separations)


An embedded system interacts with its
environment, which may span over a large area


Avoid long distance (delay) communication
Localize computation tasks
Communication costs among different locations
may be quite high (due to implementation,
noise, delay, etc.)

Minimize communication links and depths
Problem formulation

Given a computation task
T(I,O) , two physically
separated parties A(I1,O1)
and B(I2,O2) want to
fulfill task T using
minimum amount of
communication within a
specified depth

Assume X1  X2 = X and
X1  X2 = ,
where X = {I, O}
A
B
O1
O2
fa(I1,y)
fb(x,I2)
I1
x
y
h(I1,y)
g(x,I2)
I2
Prior work


Communication complexity
has been intensively studied
in the community of
theoretical computer
science since 1979
Yao’s formulation is the
most well-studied


Assume the two parties in
communication have
unbounded computation
power
Use protocol tree to represent
the communication behavior

The height of tree = bits
communicated
f
I2
I1
00
01
10
11
00
1
0
1
1
01
0
0
0
0
10
1
0
1
1
11
0
0
1
0
I1
{00,10 : 01,11}
I2
{01 : 00,10,11}
I2
{00,01,11 : 10}
0
0
1
I1
{01 : 11}
0
1
What has been missing ?


Communication depths
Sharing of communication links
Categorization



Combinational instances with one-sided outputs,
i.e. (O1 = O, O2 = )
Combinational instances with two-sided outputs,
i.e. (O1  , O2  )
Sequential instances (finite-state machines)
Combinational instance:
One-sided output (O1 = O, O2 = )

Reduce functional matrix representation



Merge identical rows and columns
Equivalent communication complexity analysis
Use multi-valued representation for multi-output
functions
f1
I1
f1'
I2
00
00
01
10
11
1
0
1
0
01
0
0
0
0
10
1
0
1
1
I2'
11
1
I1'
0
1
2
0
1
0
1
1
0
0
0
2
0
0
1
0
1
0
Combinational instance:
One-sided output (O1 = O, O2 = )

Communication depths should be captured in
embedded system design

Assume the two parties in communication have
unbounded computation power. This is fine even for
A
B
combinational implementations.
A
A
B
B
f1(I1,y')
f1(I1,y)
f1(I1,y)
g(x,I2)
g(I2)
I1
I2
(a)
h(I1)
I1
I2
(b)
I1
I2
(c)
Combinational instance:
One-sided output (O1 = O, O2 = )

Slicing functional matrices
vs. building protocol trees


Limited alternating
communication
Lower bounds


Depth-1, lg (#column)
Depth-k, minall protocol { i=1,…,k
lg (max #branch at level
i) }
Combinational instance:
Two-sided output (O1  , O2  )


Reduce functional matrix representation
Use multi-valued representation for multi-output
functions
I2
I1
00
0
1
I2
f1
1
0
01
0
0
10
1
0
f2
I1
0
1
0
row merging
00
1
1
01
0
1
f1
f2
10
1
0
f2
f2
11
0
1
11
1
I1
I2
column merging
Combinational instance:
Two-sided output (O1  , O2  )

Sharing communication links may result in
combinational cycles


Sometimes is essential to achieve minimum
communication
Might possibly have ambiguous causalities (cause bistable, oscillation behaviors)
Sequential instance

Degenerate state equivalence relation between
two parties in communication



Take advantage of this partial information to reduce
interaction
Compute partial information by Galois connection
Approximate by combinational techniques
Conclusions and future work


We give a formulation for the analysis of the
depth-bounded communication complexity
problem
Effective techniques need to be explored


Language equation formulation ?
Game-theoretic formulation ?


Nash equilibrium may not even be local optimal for selfish
row and column players
Cooperative games