Compiler optimizations in the
scalar world have, many researchers believe, run their course. We're
squeezing about as much performance as we can out of a single processor, at
least in terms of compiler techniques. The result is that the most active
area of compiler research addresses parallel computer architectures, at both
the fine-grained or instruction level and at the more coarse-grained or
distributed level. One observation is that many of the existing compiler and
optimization techniques can be adapted to benefit parallel architectures,
sometimes with unexpected benefits. The focus of my research follows this
Purpose: Development of
a nanocompiler for a hypothetical nanocomputer, which involves proposing
such a nanocomputer.
Researchers: Tom Way,
Sateesh Venkata, Purushotham Ch
Research alumni: Bryan
Wagner (nanogates), Danielle Manning (nanocomputer design), Jim Price
(quantum computing), Tao Tao (nanogates in CPN), Rushikesh Katikar (Cell
directions of computer architecture, compilers and how computers are used to
An exciting and highly interdisciplinary technology called
Nanotechnology is just now reaching the earliest stages of practical application. It is at the stage in
its development roughly analogous to World War II and computer technology.
In a mere 60 years, computers that once took up whole rooms now fit in a pocket.
And the pace of advancement has quickened as we have become more adept and
developing it. It is
predicted that Nanotechnology, also known as Molecular Manufacturing,
will be the next major breakthrough in manufacturing technology.
If forecasts are correct, it will be bigger than the Assembly Line,
the Printing Press and the Internet put together! And we will definitely
see it mature during most of our lifetimes!
Nanotechnology is about building things from the atom up.
Imagine taking the raw elemental materials (atoms of carbon, oxygen, hydrogen,
etc.) and constructing molecules from these, and mass-producing all of
the needed molecules in just the right proportions, positions and
varieties to make a new toaster-oven or baseball or 100-foot TV screen
or an unlimited supply of flu vaccine or protein bars or toilet paper. Since all things are
various combinations of atoms pieced together in just the right way,
if we can master just how to do the piecing-together part, we can
theoretically build mass quantities of just about anything very
However, that's "crazy talk." Much as Artificial Intelligence was
over-promoted during its earliest days as the next "killer app," where our
computers would become smarter than us and do all of our work for us and talk to
us and understand, it is for certain that Nanotechnology will not immediately
cause a free and limitless supply of all variety of things. But
Nanotechnology will do a lot, helping to engineer new medicines,
materials and computers that we have no other way now to create.
Leading the field of nanotechnology is
K. Eric Drexler, founder
of the Foresight Institute. Dr.
Drexler wrote the seminal document on the field,
Engines of Creation, which jump-started a science that had been
written about and
forecast for years by such luminaries as Ralph
Merkel, Marvin Minsky and
Nobel laureates Richard Smalley and
Richard Feynman, among others. The work of these people inspires my
research into a small part of an amazing new field of interdisciplinary science.
Our research in this area involves the development of a compiler for
a hypothetical nanocomputer. A nanocomputer is distinct from a
typical computer because it is created at the time it is needed based
on what it is needed for. The computer program will determine
what the nanocomputer looks like, so a "nanocompiler" will translate a
human-written computer program into the instructions to first build
the corresponding computer, and then run the program on this
custom-built computer. A nanocomputer can be massively parallel
in design, having many thousands, millions, or even billions of
processors to handle the computation. It can also be reconfigurable, either at
compilation time (old-style) or at runtime (new?), similar to the area of Field
Programmable Gate Array (FPGA)
The nanocompiler we are developing is distinct from the "nanocompiler", or
"assembler", which is the
molecular-scale mechanical device that translates assembly
instructions for a
object of some sort into the object itself using the raw atoms and
molecules as building blocks. Our use of the term "nanocompiler" is
particular to the computer science field of compilers, the computer programs that
translate a human-readable or source code program into the binary code that runs
on a computer. We would love to avoid future confusion by selecting a
better term, so part of our research will be to find the best term to express the
goals of my research.
Major issues in building a nanocompiler include identifying the
requirements of the target computer (functional units, memory
architecture, instruction set, etc.), and a major component of that
involved recognizing, or even generating, parallelism within the
program to make more efficient use of such a flexible technology. As with
much of compiler research, the precise details of the target computer are less
important than its general characteristics... but even the general
characteristics of a hypothetical nanocomputer, as well as the specifics such as
carbon nanotube logic
gates, are so interesting and yet poorly
understood, that this should be a very rewarding and enjoyable area in which to
- Compilation for Reconfigurable Nanocomputers - Assuming the
potential for flexible reconfigurability of nanocomputers, including numbers
of functional units, memory structure and hierarchies, registers, etc., this
project explores the development of a compiler that analyzes source code to
generate an optimal-as-possible architecture for that code. Issues to
explore include direct hardware implementation of code fragments versus more
general-purpose processor design, flexible ISA (and therefore
microarchitecture) design, functional unit replication, parallel pipelining,
etc. This project involves surveying the area of compiler analysis for
machine-specific applications, and the implementation of a static (and
possibly also a dynamic) analysis and machine-description-generation module
for an existing research compiler framework, conducting experiments, and
writing them up.
- Nanocomputer architecture - What are likely organizations of a
nanocomputer? What kind of memory, processor(s), communication, parallelism,
reconfigurability, low-level technology, chemical and biological and physics
concepts, compiler techniques, instruction set, etc. will it use? This project
involves surveying the literature in the subject area, and crafting (on paper)
a nanocomputer, explaining what it might look like an why. It also involves
construction of models using Colored Petri Nets, NanoEngineer, or other
tools to further quantify and explore our ideas.
- PRAM modeling - Develop a set of
Colored Petri Net (CPN) models that can simulate the theoretical PRAM, which
is useful for parallel algorithm study and research. If realistic
constraints on the PRAM models can be included, it may be possible to use
these models as the hypothetical nanocomputer architecture. The idea would
be to analyze a program and emit the appropriate PRAM on which the program
would be run.
- Parallel architecture simulator - Find the best, most flexible,
free & open source compiler & simulator framework, install it on our Linux
research machine (Links: Trimaran (here),
Parallel Computing Archive). We already have Trimaran installed and
running, and it might be sufficient, but we want to be sure. The "best"
system will allow a machine to be generated after analyzing the source code
that will be run on the new machine, and then that machine description can
immediately be used to simulate the new machine as it runs the compiled source
code program. I think Trimaran can do this.
- Reconfigurability - What are the unique capabilities that only a
nanocomputer, one that is potentially reconfigurable at run-time and
compilation-time, might exhibit? Does a nanocomputer hold this
potential, and if so, what would it be like? What issues does it raise
that need to be solved? This project involves surveying the subject,
exploring how nanotechnology might enable more powerful reconfigurable
computer architectures (sort of FPGA on steroid), and to propose how such an
architecture might work, pointing out its potential strengths, weaknesses and
- Automatic Parallelization - Since a nanocomputer is likely to be
flexibly configurable, and very likely to be parallel (and perhaps massively
parallel), the classic parallelizing compiler research can be dusted off and
brought up to date, and then applied to this new form of computer
architecture. This project involves surveying the subject area to see
what has been done before, proposing an application to a hypothetical
nanocomputer, and perhaps implementing an automatic parallelization component
within an existing research compiler framework and conducting experiments.
- Spring 2009 - Use NanoEngineer or
construct a working model of a NAND gate (or other logic gate). First, model
Drexler's NAND gate, then model other approaches. Write up for submission to
a conference as "Design of a nanoscale NAND gate using NanoEngineer".
Also, update, revise and submit "Compiling Mechanical Nanocomputer
Components" from a pervious journal submission, or make use of its results
in a current paper.
- Summer 2009 - Determine how to
programmatically generate NanoEngineer or Processing models where NAND gates are connected
into basic computational components, such as an adder. Explore the use of a
compiler to generate these from a source code input program. Write up and submit.
- Summer 2009 - Extend Rushikesh's
Cell Matrix research to implement complete compilation of a small C program
(e.g., matrix multiplication) to a Cell Matrix configuration. Then, get it
to work on a few more small C programs. Gather compile-time and run-time
statistics, write-up, submit to conference or journal (tbd). Investigate
what it would take to extend this to Java input in the future, as well.
- Fall 2009 - Investigate more deeply source code
analysis that generates a profile of needed resources for a given program (memory:
ports, size, cache arch, local, shared, distrib; registers: number, ports,
temp; ISA: common instr sequences, meta-instr creation, dynamic machine opt).
Implement using tools tbd, with either C or Java source input, and try to
run as many "real" benchmarks through analysis. Write-up and submit.
- Spring 2010 - Design of programming or assembly language
for nano-assembly (in this case, of nanocomputers), essentially an assembler ISA,
using MolML or other molecular assembly language as a foundation, determine what
NanoEngineer uses. Goal would be to go from a high level object description
language to the low-level assembly instructions to molecularly assemble the
Mechanical Logic Gates:
Reconfigurable architecture links & papers:
Nanotechnology papers and other links:
Nanomachines using NanoEngineer-1 - online technical report
CalTech nano group -
publications on nanoelectromechanical systems and other related nano-based
17 Architectures and Simulations for Nanoprocessor Systems Integrated on the
Molecular Scale - Excellent survey paper from Mitre
Phoenix Project - Reconfigurable nanotechnology at CMU, Faculty:
Seth Coppen Goldstein (Assoc.
Two Types of Mechanical
Reversible Logic - R. Merkle, Nanotechnology, Volume 4, 1993, pp.
The Next Big Thing is Really Small - Jack Uldrich, Deb Newberry, book
about nanotechnology and its effect on business.
Design of a
Primitive Nanofactory - Chris Phoenix, Journal of Evolution and
Technology - Vol. 13 - October 2003. (pdf)
1989 Proceedings - extensive writings from 1989 conference,
nanocomputing, challenges, etc.
Nanotechnology - article by Ralph Merkle, introducing and summarizing
- article from 1998 PC World magazine about nanotechnology applied to
Effect of Reconfigurable Units... - paper about reconfigurable superscalar
An Introduction to Reconfigurable Computing - overview paper, pdf.
Nanocomputer Architecture - paper about nanocomputer architecture, pdf. (acm)
- Towards a
Reconfigurable Nanocomputer Platform - paper about nanocomputers from EE
and CE perspective, pdf.
- Nanocomputer Design
Ditches Clock - article about low-power and other design aspects.
Nanowire Crossbar Structures for a Chemically Assembled Electronic
Nanocomputer - creating molecular switches
Nanotechnology, quantum information theory and quantum computing -
and Bio-Inspired Computer Engineering - features of biological entities
applied to computer arch.
Information-theoretic synthesis of nanocomputers - design and analysis of
nanocomputers and their structures
Matrioshka Brain - megascale structure constructed at atomic scale limits,
somewhat "out there" (at least for now)
Technology-Independent Model for Nanoscale Logic Devices - modeling
nanoscale logic devices, limits, etc.
- PipeRench: A
Reconfigurable Architecture and Compiler - general practical
Theoretical Models of Nanocomputers - reversible 3D mesh computer is the
best (working draft)
Computing at the Molecular Level - general trends in miniaturization,
survey of molecular level solutions
Introduction to Nanotechnology - slides of a talk
Neuroscience, neuroachitectronics, nanocomputers and nanotechnology -
mapping brain to computer, math. models
The Library of Congress in your Pocket - interesting overview-level
What Makes a Good Molecular Scale Computer Device? - design of logic
circuits at molecular level
Nanotechnology and Cyberspace: Two roads to the same city - provocative
link between the two and what lies ahead
Molecular Electronics: From Devices and Interconnect to Circuits and
Architecture - nanoscale circuit design
- Coarse grain
reconfigurable architecture - survey of reconfigurable hardware and
compilation technology, future trends
- NASA Applications of
Molecular Nanotechnology - good general article from "The World of Nano-Tech"
Cell Matrix: an architecture for nanocomputing - a nanotech-compatible
- Helical Logic
- storing 1s and 0s at the molecular level, presence or absence of an electron
Estimation of Future Manufacturing Costs for Nanoelectronics Technology -
MS thesis predicting costs of nanotech
HP: we have the next transistor - brief article about HPs molecular logic
Paradigm - massively parallel fine grained self-reconfigurable
FPGA research and info
- Altera - University program education
- Xilinx - FPGA kits
- Impulse - C programming tools for
- Mitrion - compiler
for simulation of CPU on FPGA so CPU-targeted app can run on that FPGA (article)
Exploration - Liberty Research Group at Princeton.
High-order modeling and
automated design-space exploration - paper from
Gigascale Systems Research Center
Programming Language & Compiler Research Groups - list at CMU.
Optimization Space Exploration - Spyridon Triantafyllis, Manish
Vachharajani, Neil Vachharajani, David I. August, Princeton University, CGO
Project - Univ. of Texas at Austin development of EDGE (Explicit Data
Graph Execution) architecture software (simulator?), due late Fall 2005.
Architectures and Compilers to Support Reconfigurable Computing - João M.
P. Cardoso and Mário P. Véstias, ACM Crossroads, Computer Architecture, Spring
- Cameron Project -
compiling C to FPGAs, Colorado State University, Willem Bohm, Ross Beveridge,
Bruce Draper, applicable work, good links and resources.
Coarse-Grain Parallelism Using an Interprocedural Parallelizing Compiler -
Mary W. Hall, Saman P. Amarasinghe, Brian R. Murphy, Shih-Wei Liao, Monica S.
Lam. Stanford University.
- Coarse-Grain Task Parallel Processing Using the OpenMP Backend of the
OSCAR Multigrain Parallelizing Compiler - K. Ishizaka, M. Obata, H. Kasahara,
Waseda University, Japan. (pdf
Cache Optimization for Coarse Grain Task Parallel Processing using Inter-Array
Padding - Kazuhisa Ishizaka, Motoki Obata, and Hironori Kasahara,
Department of Computer Science, Waseda University, Japan.
- Dr. Alex Niolau - U.C.
Irvine professor specializing in parallelizing compilers and reconfigurable
computing, among other areas.
Coarse-grain Pipelining for Multiple FPGA Architectures - Heidi Ziegler,
Byoungro So, Mary Hall, Pedro Diniz, University of Southern California.
Compilation to a Coarse-grained Reconfigurable System-on-Chip - Girish
Venkataramani, Carnegie-Mellon University and Walid Najjar, University of
California Riverside and Fadi Kurdahi, Nader Bagherzadeh, University of
California Irvine and Wim Bohm, Jeff Hammes, Colorado State University.
- Brian J. d'Auriol,
Ph.D. web links - CS professor at University of Texas at El Paso, links
(and interests?) include parallelizing compilers, parallel computing,
- CPC 2003 - Compilers for
Parallel Computers conference program, Amsterdam, The Netherlands, January
Linux Parallel Processing HOWTO - Hank Dietz' interesting collection of
info about parallel processing under Linux. Includes interesting article
on the "death"
of parallel processing a few years ago.
Commutativity Analysis: A New Analysis Technique for Parallelizing Compilers
- Martin Rinard (MIT), Pedro Diniz (USC).
- Blob Computing overview
- new potential way to perform parallel processing.
- Seth Copen Goldstein -
interests include computer architecture and nanotechnology.
MPI Backend for an Automatic Parallelizing Compiler - IEEE computer.org
Group Cluster Development Kit - commercial Linux cluster software and
and Parallel Computing Resources - list at CMU
- Identify, specify, describe a reconfigurable
- Identify compiler issues for nanocomputer
- Design compiler module, theory, etc. - what
are the phases of compilation?
- Experimentation, compare with other HPC
architectures (implementation on Trimaran platform)
- Lexical analysis (scanning)
- Semantic analysis
- Code generation
1st generation compilation using a Nanocompiler
- Traditional compiler: Scan, parse, semantically analyze source program
- Parallelizing compiler: Analyze code, identify opportunities for
parallelization & generate optimal machine description
- Nanoassembler: Translates machine description into custom nanocomputer
that implements source program, or on which the source program can be run
2nd generation compilation using a Nanocompiler
- Perform 1st generation compilation
- Run the program
- During runtime, continuously analyze computation and adapt machine
dynamically to improve performance