Thursday, September 10, 2015

Designer Chips

A computer architecture researcher talked to me about a role theoretical computer science can play for them: creating a new kind of computer processor. Microprocessors stopped getting faster a decade ago due to energy challenges so computer architects look for new ways to improve performance, moving away from the general-purpose CPU towards processors that handle more specific functions. The GPU, Graphics Processor Unit, has long been around to handle the graphics-intensive needs of modern computers and many have used GPUs for other purposes such as machine learning. These days we can program chips using FPGAs (Field-programming gate arrays) and are nearly at the point of cheaply compiling directly to hardware. How does this change the theory we do?

What kind of specialized chips would speed up our algorithms? If we want to find matchings on graphs, for example, is there some routine one could put in a chip that would lead to a much more efficient algorithm?

On the complexity side, how do we model a computer where we can program the hardware as well as the software? What are the right resource bounds and tradeoffs?

In general our notions of computers are changing, now with multi-core, cloud computing and designer chips. Not only should we focus on applying theory to these new models of computing, but we should think about what future changes in computing could yield more efficient algorithms. Theorists should be involved in planning the future of computing and we're not even doing a great job reacting to changes around us.


  1. This year we had a paper in TAMC where we propose a CPU with an ultra-wide word (think 10,000 bits) ALU. We showed how using sequential word RAM algorithms when can obtain speed ups comparable to difficult-to-program multi-threaded solutions on current hardware.

    Interestingly enough, when we first proposed this our wide word was 150x larger than the typical ALU in practice. Today it is only 40x larger.

  2. Not sure about your "not reacting" comment.