‘Oracle’ Computer Could Hold All the Answers

Instead of waiting weeks for computers to grind out solutions to complex problems, scientists may someday get answers instantly thanks to a new type of "oracle" computer that will have all the answers built in, Duke computer scientists and engineers predict. When a question is posed, the computer will provide the answer already paired with the question in the very structure of the computer's processing unit.

"We call this kind of computer an oracle because, like the oracles of ancient times, the computer is ready to answer your question as soon as you ask," said Chris Dwyer, assistant professor of electrical and computer engineering and computer science at the Pratt School of Engineering.

Dwyer said oracle processors will consist almost entirely of vast numbers of question-and-answer pairs. "At run-time, there will be no need to start from scratch, run a program, input data and perform computations," Dwyer said.

(L-R) Daniel Sorin, assistant professor electrical and computer engineering; Chris Dwyer, assistant professor of ECE; and Alvin Leback, associate professor of computer science.

Futuristic fabrication techniques that use DNA molecules to assemble vast numbers of electronic circuits simultaneously will make oracle processors feasible over the next decades, Dwyer said.

"DNA self-assembly holds the promise of automatically producing trillions of electronic devices," he said. "That's why we can think about computing every solution to some kinds of problems, when the computer is being assembled and building the answers in."

Dwyer said such problems could at first include plotting efficient shipping routes and might eventually be extended to solving general optimization problems such as computing the best schedule, designing the most efficient network and storing and retrieving data in the shortest possible time.

Coaxing strands of DNA into first building practical electronic circuits and then large-scale computers will not be easy, Dwyer said. The technique of "DNA self-assembly" takes advantage of the way complementary DNA strands always bind together according to the same rules -- like complementary puzzle pieces fitting together. By creating selective DNA strands with "tags" that stick only to a desired location on another strand, scientists can launch a process that assembles the desired structure. The next stage of fabrication deposits metals or other conductors on the structure to complete the circuit.

"The same DNA binding rules can be used to actually compute results to problems," Dwyer said. "That's why it's possible to think about computing all the solutions for a problem at fabrication time."

"There are many challenges to overcome, but the oracle processor concept is powerful and attractive," said Alvin Lebeck, associate professor of computer science and electrical and computer engineering. "Today's computers do most of the work long after they are built, when the user submits a problem, loads data and waits. The oracle approach does most of the work long before the user even sits down at the computer, back at the time of fabrication."

Lebeck said semiconductor technology is poorly suited to such an approach. Storing all the answers in a silicon chip would require a chunk of silicon far too large for foreseeable manufacturing methods. "Today's computers have great flexibility because programmers can write code that lets users enter new information and get a new answer. Unfortunately, solving some problems takes weeks or months."

DNA self-assembly is in its infancy, with many unresolved challenges, but it opens new possibilities, Lebeck said. "It has the potential to build processors such as the oracle that could solve some important problems with unprecedented speed," Lebeck said.

Dwyer, Lebeck and their colleague Daniel Sorin, assistant professor of electrical and computer engineering and computer science, described the potential for shifting much of the computation to the time of fabrication in their paper, "Self-Assembled Computer Architecture and the Temporal Aspects of Computing," in the January 2005 issue of IEEE Computer Magazine. The paper is part of the issue's cover feature on "bleeding edge" developments.

Lebeck is principal investigator on a long-term project funded by the National Science Foundation to move DNA self-assembly beyond the bleeding edge and actually construct an electronic computing device through DNA self-assembly.

According to Lebeck, the project is named Troika because it must balance three competing considerations in building DNA self-assembled computers: the regularity of the patterns such assembly can create, the variations needed to build complex computers, and techniques for overcoming the defects that are inevitable in self-assembly.

The Troika project includes Duke faculty members John Reif, Thom LaBean and Hao Yan in computer science and Jie Liu in chemistry; Sean Washburn and Dorothy Erie of the University of North Carolina - Chapel Hill; and Paul Franzon of North Carolina State University. Duke graduate students Vijeta Johri, Jaidev Patwardhan, Sung-Ha Park, Nathan Sadler and Niranjan Soundarajan are also contributing to the project.

"Realistically, we don't expect practical DNA self-assembled computers for a decade or more," Lebeck said. "But before you can arrange for DNA to assemble a computer, you have to understand what sort of computer you want the DNA to assemble. The oracle architecture is a promising step in that direction."

Dwyer is principal investigator, with Lebeck as co-principal investigator, on a grant from the Air Force Research Laboratory to investigate the potential of oracle-type computations. Dwyer said he started thinking about DNA computing in his college years after reports of computer scientist Leonard Adleman's 1994 demonstration of using DNA binding followed by chemical processes to compute a solution to a problem. "I just couldn't stop thinking about it," Dwyer said. Adleman is at the University of Southern California.

The possibilities of the oracle approach struck Dwyer while he worked on his doctoral dissertation at UNC - Chapel Hill. He had been thinking for some time about "placing DNA computing and conventional computing in the same frame and seeing if there were natural connections. And the push from the self-assembly side of things, with the potential for huge manufacturing scale, came to be a strong motivator because it hinted something big was possible. It still is."

Dwyer said he has always liked building things. "I was a math/chemistry/physics nut as a kid - chemistry kits, pyromania, the whole bit," said Dwyer. "I bought an arc welder when I was 14 to build a submarine. I was always on some project that I couldn't finish. That's what I wanted most from my Ph.D., to finish something big."

With the dissertation complete, Dwyer said, "I'd like to help finish something bigger, a working electronic computer assembled by DNA."