Matthew I. Frank

Research Interests

Education

Honors

Employment

Architecture Projects

PolyFlow: 2003-present

PolyFlow is a dynamic dataflow processing system that automatically and dynamically converts sequential binaries into multithreaded code. One of the primary insights we've gained from the experience is that such systems are most effective when they create threads to maximize what we call "branch mispredict level parallelism," or BLP. Because each thread of control has its own program counter, branch mispredicts in one thread don't necessarily stall fetch and execution in other threads. On the other hand, we were surprised to discover that branch speculation within threads is at least as important as in the sequential domain. This is because branches require data (often data produced by another thread) in order to resolve. Branches that can be correctly predicted no longer depend on the latency of inter-thread data communication and synchronization.

Illinois Cubesat: 2003-present

I have been one of three advisors for the University of Illinois's ION (Illinois Observing Nanosat) Cubesat project, an interdisciplinary undergraduate design course sponsored by the College of Engineering. In Cubesat, undergraduate students build their own "nano-satellite." The first product of this class, the ION-1, was a 2-kilogram, 2- liter atmospheric observing satellite. It was delivered to the launch company, Kosmotras, in Fall 2005 and launched in Summer 2006. The design and fabrication of the satellite were accomplished entirely by students, mostly undergraduates with an occasional Master's student. I supervised the students designing the operating system and control software.

Based on our experience with testing and integrating ION-1, several students and I began the design of a general-purpose, reusable platform that allows modular integration of multiple sensors and actuators. In the Fall 2006 semester I guided a dozen undergraduates through the design and fabrication of a 10 x 14cm "motherboard" that included several Microchip PIC processors that drove both an I2C bus and a 9600-baud digital communication system. We also developed a software protocol so that future Cubesat students can easily design instruments that will plug directly into the bus to leverage the communication and storage facilities of the motherboard. During the Spring 2007 semester we built infrastructure for and launched a simple weather balloon as a platform for testing student designs in preparation for the future launch of ION-2.

MIT Raw Multicore processor: 1996-2002

I was one of the lead students (with Mike Taylor, Jon Babb and Walter Lee) on the Raw Microprocessor project from 1996-2002. Raw was one of the first general purpose multicore processor chips. It had 16 32-bit cores, each with 64Kbytes of cache. I specifically contributed to the design of the compilers, the memory system and the deadlock management system in the interconnect. I also supervised several projects researching memory system micro-optimization, including a software-based instruction cache management system and FlexCache, a method of improving data cache efficiency by using the compiler to eliminate unneeded cache tag checks.

MIT Fugu Multiprocessor: 1994-1996

I assisted in the design and implementation of the MIT Fugu scalable shared memory multiprocessor system. I implemented and maintained portions of the operating system and system simulator and contributed to the design and evaluation of scheduling algorithms to maximize performance of interactive jobs.

Software Projects

Illinois IPA Simulator Toolkit: 2003-present

I designed and wrote the initial version of a flexible and detailed microarchitectural simulator toolkit that has served as my group's research infrastructure for the past five years. The toolkit has been the primary experimental vehicle for two PhD theses and over a dozen masters theses in addition to scores of semester projects in the graduate architecture and microarchitecture classes at University of Illinois since 2003.

The toolkit simulates a 64-bit MIPS-like ISA, supports simulation at several levels of detail and can checkpoint machine state. The toolkit's primary design goal was instructional. Simulated instructions flow through the software modules in the order that they would flow through the microarchitectural pipeline stages. This makes it easier for students to understand the simulator/microarchitecture mapping. To identify bugs quickly, the simulator executes instructions out-of-order (in the order they would execute on the microarchitecture being simulated) and checks instruction results against a dynamically generated trace as instructions retire. At its highest level of detail the toolkit is still relatively fast, able to simulate a two-wide out-of-order processor at about 100K cycles/second.

EZ32 C Library: 2000-present

I wrote and still maintain a small, not-quite standard, C Library that is notable for its support of machines that have only 32-bit floating point hardware (common in academic microprocessor design projects). Parts are derived from Cygnus Newlib (an open source C Standard Lib for embedded systems), but most of the code is hand-rolled, in particular the code for scanning and printing floating point strings. It also includes an efficient best-fit malloc implementation. This was the C Library used on the Raw Microprocessor at MIT, for the Polyflow project at Illinois and now for the 10 TFlop Rigel accelerator chip being designed at Illinois.

SUDS, the Software UnDo System: 1998-2002

I designed and built the SUDS Runtime system, a complete software transactional memory system that ran on the Raw multicore. SUDS was designed to enable speculative loop transformations. The parallelism enabled by those transformations often provided speedups despite a relatively large software overhead of about 20 machine cycles per speculative load operation.

The SUDS compiler, built as a set of modules on the Stanford SUIF 1.3 compiler system, performed parallelism enhancing loop transformations. By performing loop distribution, scalar expansion and reassociation on a program dependence graph representation of the program the compiler could find and expose parallelism in a wide variety of loops, including loops that worked on sparse data structures or contained complex internal control.

I was also the primary local maintainer of version 1.3b of the SUIF compiler infrastructure for a group of about 12 students and faculty at MIT after Stanford stopped supporting version 1 to work on the (abortive) SUIF version 2. I completely rewrote the build system and fixed dozens of bugs in the core libraries.

Gizmoball: 1999

As a teaching assistant I designed and implemented the semester project for the Spring 1999 offering of MIT's Laboratory in Software Engineering, a junior level course. Gizmoball was a pinball game that included an editor that allowed the user to place bumpers and flippers, and connect flippers to triggers to create various "Rube Goldberg" contraptions. I prototyped the project, wrote the assignment (basically a specification) and implemented, documented, and supported a physics library that used spatial hashing to perform collision detection and then calculated the forces from impacts. The project was reused, with variations, every semester for the following four years.

CDLBIEM: 1992-1994

Worked with a team of Chemical Engineering Students implementing parallel N-body codes on the Thinking Machines CM-5 at the University of Wisconsin. In addition to writing application code I was responsible for debugging and maintaining the local installation of the experimental Berkeley Split-C programming tools.

Harvard Draw: 1990-1992

I designed and implemented testing and debugging tools for the team developing Software Publishing Corporation's Harvard Draw program. Among other projects I implemented a straight-forward, but effective, memory leak detector.

Information Management Systems: 1986-1987

I was responsible for designing and maintaining all the information management systems at SoftCraft, a small (40 employee) company in Madison Wisconsin.

Refereed Publications

Unpublished

Invited Lectures

• System Support for Implicitly Parallel Programming, University of California at Berkeley, April, 2008.
• Microarchitectural Support for Automatic Parallelization, MARCO/FCRP Center for Circuits and Systems Solutions Workshop on Microarchitecture, February, 2007.
• Microarchitectural Support for Automatic Parallelization, University of Texas at Austin, January, 2007.
• Scalar Queue Conversion, Intel KAI Software Lab, Champaign, IL, April 2003.

Courses

M.S. Students

Wei-Ping (Thomas) Soong, December 2003, Intel, Austin, TX; Thomas R. Novak, May 2004, AMD, Sunnyvale, CA; Daniel Hodges, December 2004, EDS, Dallas, TX; Benjamin J. Miller, January 2005, AMD, Boxborough, MA; Michael D. Tucknott, January 2005, Intel, Hillsboro, OR; Michael J. Dabrowski, May 2005, SpaceX; Kevin M. Woley, December 2005, Microsoft, Richmond, WA; Snehal Sanghavi, January 2006, AMD, Sunnyvale, CA; Kevin J. Stephano, May 2006, AMD, Austin, TX; Hing Lim Chan, May 2006; Kshitiz Malik, December 2006, (continued); Mayank Agarwal (CS), December 2006, (continued); Brandon K. Swamy, May 2007, AMD, Austin, TX; Christopher R. Burke, May 2007, AMD, Austin, TX; Sam S. Stone, July 2007, Harvard Law; Nitin S. Navale, December 2007, AMD, Sunnyvale, CA; Idan Lupinsky, Goldman Sachs, December 2007; Vikram Dhar, May 2008, NVIDIA, Santa Clara, CA; James S. Pike, May 2008, Microsoft, Redmond, WA; Lukasz R. Lempart, Riverbed, May 2008; Gene Wu, July 2008; Ali A. Hussain, Fall 2008 (expected); Nicholas R. Weaver, Spring 2009 (expected).

Ph.D. Students

• Kshitiz Malik, summer 2008 (expected)
• Mayank Agarwal (CS), 2009 (expected)

External Funding

Professional Activities

• NSF Panels: Dec 2004 and March 2007.
• Program Committees:
  • Int'l Symp Comp Arch (ISCA-35), 2008.
  • ACM Conf on Prog Lang Design and Implementation (PLDI), 2008.
  • Int'l Conf on Compilers, Architecture and Synthesis for Embedded Systems (CASES), 2007.
  • Int'l Symp on Code Generation and Optimization (CGO-5), 2006.
  • 5th Int'l Symp on High Performance Computing, 2003.
• Referee for ISCA, MICRO, ASPLOS, PLDI, HPCA, SIGMETRICS, SOSP, IPDPS, ACM Transactions on Computer Systems, IEEE Computer, IEEE Transactions on Parallel and Distributed Systems, ACM Transactions on Architecture and Compiler Optimization, IEEE Computer Architecture Letters.