Designing the hardware

Feb 23, 2011 by Larry Hardesty
Graphic: Christine Daniloff

Computer chips' clocks have stopped getting faster. To maintain the regular doubling of computer power that we now take for granted, chip makers have been giving chips more "cores," or processing units. But how to distribute computations across multiple cores is a hard problem, and this series of articles examines the different levels at which MIT researchers are tackling it, from hardware design up to the development of new programming languages.

With the multicore chips in today's personal computers, which might have four or six or even eight cores, splitting computational tasks hasn't proved a huge problem. If the chip is running four programs — say, a word processor, an e-mail program, a Web browser and a media player — the operating system can assign each its own core. But in future chips, with hundreds or even thousands of cores, a single program will be split among multiple cores, which drastically complicates things. The cores will have to exchange data much more often; but in today’s chips, the connections between cores are much slower than the connections within cores. Cores executing a single program may also have to modify the same chunk of data, but the performance of the program could be radically different depending on which of them gets to it first. At MIT, a host of researchers are exploring how to reinvent chip architecture from the ground up, to ensure that adding more cores makes chips perform better, not worse.

In August 2010, the U.S. Department of Defense’s Defense Advanced Research Projects Agency announced that it was dividing almost $80 million among four research teams as part of a “ubiquitous high-performance computing” initiative. Three of those teams are led by commercial chip manufacturers. The fourth, which includes researchers from Mercury Computer, Freescale, the University of Maryland and Lockheed Martin, is led by MIT’s Computer Science and Artificial Intelligence Lab and will concentrate on the development of multicore systems.

The MIT project, called Angstrom, involves 19 MIT researchers (so far) and is headed by Anant Agarwal, a professor in the Department of Electrical Engineering and Computer Science. In 2004, Agarwal cofounded the chip company Tilera to commercialize research he’d done at MIT, and today, Tilera’s 64-core processor is the state of the art for multicore technology.

One way to improve communication between cores, which the Angstrom project is investigating, is optical communication — using light instead of electricity to move data. Though prototype chips with optical-communications systems have been built in the lab, they rely on exotic materials that are difficult to integrate into existing chip-manufacturing processes. Two of the Angstrom researchers are investigating optical-communications schemes that use more practical materials.

In early 2010, an MIT research group led by Lionel Kimerling, the Thomas Lord Professor of Materials Science and Engineering, demonstrated the first germanium laser. Germanium is already used in many commercial chips simply to improve the speed of electrical circuits, but it has much better optical properties than silicon. Another Angstrom member, Vladimir Stojanović of the Microsystems Technology Laboratory, is collaborating with several chip manufacturers to build prototype chips with polysilicon waveguides. Waveguides are ridges on the surface of a chip that can direct optical signals; polysilicon is a type of silicon that consists of tiny, distinct crystals of silicon clumped together. Typically used in the transistor element called the gate, polysilicon has been part of the standard chip-manufacturing process for decades.

Other Angstrom researchers, however, are working on improving electrical connections between cores. In today’s multicore chips, adjacent cores typically have two high-capacity connections between them, which carry data in opposite directions, like the lanes of a two-lane highway. But in future chips, cores’ bandwidth requirements could fluctuate wildly. A core performing a calculation that requires information updates from dozens of other cores would need much more receiving capacity than sending. But once it completes its calculation, it might have to broadcast the results, so its requirements would invert. Srini Devadas, a professor in the Computer Science and Artificial Intelligence Lab, is researching chip designs in which cores are connected by eight or maybe 16 lower-capacity connections, each of which can carry data in either direction. As the bandwidth requirements of the chip change, so can the number of connections carrying data in each direction. Devadas has demonstrated that small circuits connected to the cores can calculate the allotment of bandwidth and switch the direction of the connections in a single clock cycle.

In theory, a computer chip has two main components: a processor and a memory circuit. The processor retrieves data from the memory, performs an operation on it, then returns it to memory. But in practice, chips have for decades featured an additional, smaller memory circuit called a cache, which is closer to the processor, can be accessed much more rapidly than main memory, and stores frequently used data. The processor might perform dozens or hundreds of operations on a chunk of data in the cache before relinquishing it to memory.

In multicore chips, however, multiple cores may have cached copies of the same data. If one of the cores modifies its copy, all the other copies have to be updated. There are two general approaches to maintaining “cache coherence”: one is to keep a table of all the cached copies of the data, which has a cost in the computation time required to look up or modify entries in the table; the other is to simply broadcast any data updates to all the cores, which has a cost in bandwidth and, consequently, energy consumption. But Li-Shiuan Peh, an Angstrom researcher who joined the MIT faculty in 2009, is advocating yet a third approach. She has developed a system in which each core has its own “router,” which, like the routers in the Internet, knows only where to forward the data it receives. Peh’s simulations show that a network of routers is more computationally and energy efficient than either of the standard alternatives.

Whether the Angstrom project settles on electrical or optical connections remains to be seen. But Agarwal says that future multicore chips could well use both: Electrical connections would move data between individual cores; but optical connections would provide chip-wide broadcasts.

Not all the MIT faculty researching multicore architectures are affiliated with the Angstrom project, however. Jack Dennis is technically an emeritus professor, but together with colleagues at the University of Delaware and Rice University, he’s received National Science Foundation funding to research a radically different multicore architecture. In Dennis’ system, a computer’s memory is divided into chunks of uniform size, each of which can store data but can also point to as many as 16 other chunks. If a data structure — say, a frame of video — is too large to fit in a single chunk, the system creates additional chunks to share the burden and links them to existing chunks.

Dennis’ data chunks have three unusual properties. First, they are abstractions: Several chunks storing a single data structure might be found in a core’s cache, but if the cache fills up, other chunks might be recruited from main memory or even from a flash drive. The system doesn’t care how the chunks are instantiated. Second, and perhaps most counterintuitively, once a chunk has been created, it may never be altered. If a core performs an operation on data stored in a chunk, it must create a new chunk to store the results. This solves the problems of multiple cores trying to modify the same location in memory and of cache coherence. Once a chunk is no longer in use by any core, it’s simply released for general use. Another chunk, storing the result of a computation, could take its place in the network of links. Finally, because any operation of any core could result in the creation or deletion of chunks, the allocation of the chunks is performed by circuits hard-wired into the chip, not by the computer’s operating system. “As far as I know, nothing like this is going on anywhere else,” Dennis says.

Whatever the architectural challenges posed by multicore computing, however, they’re only the tip of the iceberg. The next installment in this series will begin to look at MIT research on software.


This story is republished courtesy of MIT News (web.mit.edu/newsoffice/), a popular site that covers news about MIT research, innovation and teaching.

Explore further: The internet was delivered to the masses; parallel computing is not far behind

Related Stories

Mastering multicore

Apr 26, 2010

(PhysOrg.com) -- MIT researchers have developed software that makes computer simulations of physical systems run much more efficiently on so-called multicore chips. In experiments involving chips with 24 separate ...

New hardware boosts communication speed on multi-core chips

Jan 31, 2011

Computer engineers at North Carolina State University have developed hardware that allows programs to operate more efficiently by significantly boosting the speed at which the "cores" on a computer chip communicate with each ...

AMD Planning 16-Core Server Chip For 2011 Release

Apr 27, 2009

(PhysOrg.com) -- AMD is in the process of designing a server chip with up to 16-cores. Code named Interlagos, the server chip will contain between 12 and 16 cores and will be available in 2011.

Intel's single-chip cloud computer

Feb 11, 2010

(PhysOrg.com) -- Intel Labs has recently shown off a 48-core prototype chip it calls a "single-chip cloud computer" or SCC.

Recommended for you

Hacking Gmail with 92 percent success

1 hour ago

(Phys.org) —A team of researchers, including an assistant professor at the University of California, Riverside Bourns College of Engineering, have identified a weakness believed to exist in Android, Windows ...

User comments : 4

Adjust slider to filter visible comments by rank

Display comments: newest first

jimbo92107
not rated yet Feb 23, 2011
"...it was dividing almost $80 million among four research teams as part of a “ubiquitous high-performance computing” initiative."

That's $20 million per team. Why not divide $80 million among 40 teams, giving $2 million to each? You'd get a lot more new ideas that way, and each team would have plenty of money to get a good start on its idea. Then a committee can decide which ideas are worth further development, and go from there with more funding.
Eikka
not rated yet Feb 24, 2011
There's more to the cache coherence and data sharing problem than just getting all the cores' memories updated.

For example, if a problem is too large to be handled by a single core in a given time, it has to be split, but if the subsequent parts of the task are causally related, then the other core cannot begin processing until the first has completed its part, thus making two cores working on the same problem as slow as one.

There are tricks around this, like branch prediction where one core calculates the first part of the problem while the other core calculates the second part under many different assumptions on the result of the first core. Essentially, it's a "what if" question, and once the first core has done its job, the second core has the corresponding answer ready, or at least well under way.

The problem with that approach is that it's not very energy efficient. The second core has to do much more work to deliver the result on time.
Eikka
not rated yet Feb 24, 2011
And therein comes the rub. Suppose you have a problem so large that it would require ten cores to complete in time, but each core depends on the other to deliver a result.

Even the branch prediction breaks down now, because even if each core added just a single bit to the answer, the second core has to do twice the work, the third core four times the work, and the tenth core has to calculate 1024 different permutations of the same calculation in order to have all the answers ready when the information cascades down the chain.

If each core calculates a random assumption and they can calculate 10 permutations in the time the first core completes its part, the 6th core has only 15% chance of having the right answer. If it doesn't, 10% is added to the processing time. Assuming all the cores are the same, the 8th core no longer makes things any faster.
Justsayin
not rated yet Feb 28, 2011
Hats off to Christine Daniloff for the graphic.