| Questions
Questions
CBS3 2002 | Final
Report CBS3 2002
Bacon
| DeHon | Savage
| Snider | Yurke
Wednesday,
June 16
Lecturer:
John Savage Topic:
Models of Computation
Projects:
a. Determine the number of Boolean functions on n variables.
Count the number of circuits containing k or fewer gates. Use these
facts to show that the most complex Boolean function on n variables
has circuit size at on the order of 2^n/n.
b.
Design an FSM to add 1 to a binary number that is supplied as a
binary sequence, less significant digit first.
c.
Design a TM to recognize strings of the form ww^R where w is a binary
string and w^R is its reverse.
d.
Design a 2D mesh to multiply two n x n matrices in O(n) steps.
e.
Show that a CRCW PRAM can be programmed to compute the value of
a Boolean function in a constant number of steps.
f.
Give a proof that the basis {AND, OR} is not complete.
g.
Show that every Boolean function can be expanded as the EXCLUSIVE
OR of the AND of literals (variables or their complements). Show
that in this expansion OR requires an exponential number of terms.
h.
Show how addition of two binary numbers can be realized by a one-tape
Turing machine using two tracks on its tape, one containing data
and a second containing markers.
i.
Give a complete design of a universal Turing machine. This requires
that a representation of TMs be decided upon in advance.
j.
Describe in detail the alphabet for strings that are configurations
of Turing machines.
k.
Complete the proof that a TM does not exist to solve the Halting
Problem.
go
to top of page
Friday,
June 18
Lecturer:
Bernard Yurke Topic:
DNA: Structure, Energetics, Kinetics, and Machines
[see
also reading]
Project:
Devise a DNA-based method to evaluate arbitrary Boolean functions
employing only hybridization and strand displacement. For readout,
use a set of fluorescently labeled DNA strands and a hybridization
plate that has an array of DNA strands with sequences you specify.
Hint
at a possible approach: Consider a patch a
on a hybridization plate to which DNA strands with base sequence
A have been attached. If one introduces strands having the base
sequence cAcB
where cA
denotes the complement of A
and cB
denotes the complement of B
then the cAcB
strands will hybridize to the DNA on patch a.
If one then introduces dye labeled strands B
they will hybridize to the sequence cB
of the cAcB
strands. Consequently, after the hybridization plate is washed
to remove excess B
and cAcB,
patch a will show fluorescence. Patch a will fluoresce only if
it has DNA with sequence A
and if strands B are present. Strands cAcB
can thus be regarded as a kind of "and" operator. They
link strands A
and strands B
together.
go
to top of page
Monday,
June 21
Lecturer:
Andre DeHon
[see
also reading]
Project
1: 3D Adiabatic Switching:
A common concern is that the limit to computational density could
come from power density rather than small feature sizes. Effects
of this are already being seen in conventional MOS designs. We
can contemplate 3D architectures to further extend computing density,
but this will only exacrabate the power density/heat-removal problem.
In theory, it should be possible to compute with zero energy using
reversible operations, but adiabatic circuits will require more
area than their conventional counterparts, and may need to run
very slowly to provide their net benefit. How can we combine parallelism,
3D circuit construction, and adiabatic switching to increase the
net computation which can be sustained in a given volume with
a fixed power limit? (i.e. how can we increase the net computational
density beyong traditional/naive power density limits?) * Feynman
Lectures on Computation (Chapters 5 and 7.2) * S. G. Younis and
T. F. Knight, Jr., "Asymptotically Zero Energy Split-Level Charge
Recovery Logic," in Proceedings of the International Workshop
on Low Power Design, 1994, pp. 177--182.
go
to top of page
Project
2: Runtime/Programming Language Model for Unreliable Hardware:
When gates are no longer reliable, what is a reasonable compute
model/runtime system/programming language for achieving reliable
computations on top of unreliable compute structures? As we reach
the atomic scale, it will no longer be reasonable to expect individual
gates to perform 100% reliably [LLNSD]. We can use redundancy
to increase the reliablity at the circuit level [e.g. VN,PIP].
We can allow architectural checking and roll-back [e.g. RAZOR,
SHANGBANG]. These techniques will make the probability of errors
slipping through to higher levels lower, but will not make it
zero. So, how should our higher levels of system composition and
design evolve to accommodate the fact that some errors will propagate
up and be visible at this level?
LLNSD: http://www.cs.caltech.edu/research/ic/abstracts/
llnsd_nanobook2004.html
VN: @InCollection{vonneumann_unreliable_components56,
author = {John Von~Neumann},
title = {Proabilistic Logic and the Synthesis of Reliable
Organisms from Unreliable Components},
booktitle = {Automata Studies},
publisher = {Princeton University Press},
year = 1956,
editor = {Claude Shannon and John McCarthy}
}
PIP:
@InProceedings{pippenger_unreliable_components_review90,
author = {Nicholas Pippenger},
title = {Developments in 'The Synthesis of
Reliable Organisms from Unreliable Components'},
booktitle = {Proceedings of the Symposia of Pure Mathematics},
pages = {311--324},
year = 1990,
volume = 50
}
RAZOR
SHANGBHAG
go
to top of page
Tuesday,
June 22
Lecturer:
Dave Bacon Topic:
Introduction Quantum Information: Quantum Channel Capacities
[see
also reading]
Projects:
The
Knill-Gottesman theorem states that quantum computations done
with prepared |0> states, Clifford group gate sets, and measurement
in the Z basis can be efficiently simulated on a classical computer.
On the other hand, it is known that using these operations we
can generate Bell violations (GHZ violations) and thus there is
something nonlocal about the gate sets.
Project:
find a state in the Knill-Gottesman context which requires more
than a bit of communication in order to simulate.
Project:
find a generic protocol for the Knill-Gottesman gate set which
uses as little multiparty communication as possible.
go
to top of page
Wednesday,
June 23
Lecturer:
Gred Snider Topic:
Molecular Architecture Studies I & II
[note
Greg Snider's lecture I on June 23, lecture II on June 25]
[see
also reading]
Nano-electronics
Routing Project
Hypothetical crossbar-based architectures for nano-electronics
often resemble field-programmable gate arrays (FPGAs) in that
they consist of programmable "logic blocks" embedded
within a programmable routing network. But unlike FPGAs, nano-electronic
"chips" will contain many random defects within the
crossbars, making each chip unique. Programming a single chip
will require finding the defects within it, then placing and routing
the desired circuit onto the chip's fabric in a way that works
around those defects. To keep manufacturing costs within reasonable
bounds, the entire process of defect characterization, placement
and routing must be done using efficient data structures and algorithms.
This project focuses on the routing portion of this problem.
Problem:
Devise efficient data structures and algorithms for routing signals
in crossbar architectures containing random defects. You may assume
that the locations of all defective junctions are known and available
to the router, and that the circuit to be implemented has already
been synthesized and intelligently placed onto the crossbar fabric.
You may also assume that the crossbar fabric is architecturally
regular.
Hints:
A general structure for representing routing networks is the routing
resource graph [1, 2]. The graph uses a small data structure for
each wire in the target architecture as well as a small data structure
for each programmable switch that essentially points to the data
structures for the two wires that the switch connects. This is
reasonably efficient for small FPGAs, but can consume large amounts
of memory as the size of the FPGA increases. Since most FPGAs
are extremely regular in their layout and a only a very small
percentage of available switches in the routing network are configured,
the memory requirements can be dramatically reduced using the
"Flyweight" design pattern [3] to factor out redundant
connectivity information.
go
to top of page
Simple
algorithms for routing can be found in [4, 5].
Here
are some issues to consider:
(1)
Since defects are random throughout the fabric, can the Flyweight
design pattern still be used?
(2)
Defect rates might be in the range of, say, 5% to 15%. Can you
exploit the fact that most switches in the routing network are
functional in designing your data structures?
(3)
Where are the likely bottlenecks in the routing network?
(4)
What is a good fallback strategy if your router fails to route?
go
to top of page
References:
[1] L. McMurchie, C. Ebeling, "PathFinder: a negotiation-based
performance-driven router for FPGAs," Proceedings of the
1995 ACM third international symposium on Field-programmable gate
arrays, pages 111 - 117.
[2]
C. Ebeling, L. McMurchie, S. Hauck, S. Burns, "Placement
and routing tools for the Triptych FPGA," IEEE Transactions
on Very Large Scale Integration (VLSI) Systems, Volume 3 , Issue
4 (December 1995), pages: 473 - 482.
[3]
E. Gamma, R. Helm, R. Johnson, J. Vlissides, “Design Patterns,”
Addison-Wesley.
[4]
V. Betz, J. Rose, A. Marquardt, "Architecture and CAD for
Deep-Submicron FPGAs", Chapter 4, Kluwer Academic Publishers,
1999.
[5]
http://www.eecg.toronto.edu/~vaughn/vpr/vpr.html
go
to top of page
|
