Algorithmic Foundations for Emerging Computing Technologies

The stunning rate of improvement in CMOS technology since the 1960s, captured in Gordon Moore's prediction of a doubling in transistor density every year or two (which came to be called Moore's law), has been the driving factor enabling computer architects to design faster processors. Although Moore's law held for many decades, it began to slow sometime around 2000, and now there is an order of magnitude between Moore's prediction and actual transistor density. The current expectation is that the gap will continue to grow as CMOS technology approaches fundamental limits.

Accompanying Moore's law was a projection made by Robert Dennard (which came to be called Dennard scaling) that stated that as transistor density increased, power consumption per transistor would drop proportionally, so the power per unit area of silicon would be near constant. Since the computational capability of a unit area of silicon was increasing with each new generation of technology, the result was the projection that computers would become more energy efficient. However, Dennard scaling faded to a negligible amount about a decade ago.

Due to Moore's law and Dennard scaling, during the last couple of decades of the 20th century, the exploitation of instruction-level parallelism was the primary architectural method for gaining performance. However, the end of Dennard scaling meant architects had to find more efficient ways to exploit parallelism, leading to the multicore era. These technology changes have also had an impact on the relationship between processors and memory. Historically, memory (especially hard drives) was much slower than processors, and the relative speed of memory decreased with each generation of technology. However, when Moore's law ended, memory technology continued to improve, including new types of memory technologies. Application-level parallelism is essential to saturate the throughput. 

The end of Dennard scaling and Moore's law, as well as the advent of new memory technologies, are not problems that must be solved but facts that, recognized, offer breathtaking opportunities. The next decade will see a Cambrian explosion of novel computer architectures, meaning exciting times for computer scientists in academia and in industry. The introduction of increasingly diverse device technologies, integrated in increasingly heterogeneous computer architectures, will make the efficient management of these emerging computing technologies more algorithmically challenging than the management of prior computing technologies.

This program will bring together algorithm researchers, with research interests in problems arising from managing computing systems, with architecture researchers and industrial researchers with interests in these emerging computing technologies, and who value foundational algorithmic research. The goals of the program are to identify emerging hardware technologies whose management policies could be developed using foundational algorithmic research, to develop candidate formal models for these technologies, and to establish proof-of-principle results in these models.

Organizers
Kunal Agrawal (Washington University in St. Louis), Pierre-Emmanuel Gaillardon (University of Utah), Shahar Kvatinsky (Technion), Kirk Pruhs (University of Pittsburgh), Jan Rabaey (University of California, Berkeley), Cliff Stein (Columbia University)

Long-Term Participants (tentative) 
Kunal Agrawal (Washington University in St. Louis), Sanjoy Baruah (Washington University in St. Louis), Edith Beigne (Meta), Naama Ben-David (Technion), Michael Bender (SUNY-Stony Brook), Yiran Chen (Duke University), Alex Conway (Cornell Tech), Maryam Dehnavi (University of Toronto), Martín Farach-Colton (New York University), Panagiota Fatourou (University of Crete), Pierre-Emmanuel Gaillardon (University of Utah), Phil Gibbons (Carnegie Mellon University), Udit Gupta (Cornell Tech), Sharon Hu (Notre Dame), Sungjin Im (UC Merced),  Rob Johnson (VMware), Hai Li (Duke University), Nicole Megow (University of Bremen), Ian O'Connor (École Centrale de Lyon), Kirk Pruhs (University of Pittsburgh), Rajmohan Rajaraman (Northeastern University), Cliff Stein (Columbia University), and Elena Vatajelu (University of Grenoble)

To participate as a fellow, please apply here.

To participate as a long-term visitor, please apply here.