Front Page

The Liberty Research Group

The Structural Modeling Project

[David August is responsible for this page]

For over a decade, many prominent computer architecture researchers have documented the various ill effects of the most prevalent modeling methodology employed in systems design and research, the hand-writing of monolithic simulators using sequential programming languages. They have noted that this methodology hinders the exploration of radical ideas, creates barriers to collaboration, makes the validation of research results in general contexts extremely rare, leads to frequent introduction of unintended inaccuracies, and slows progress with its high recurring model development costs (which appear to many as unnecessary given the similarities among models). [MICRO 2002] While many were acknowledging these ill effects, we decided to directly examine the cause of these effects and to launch a multi-year research effort to find a solution.

Our exploration of existing architectural modeling methodologies, which included interviewing processor designers and analyzing solutions to design problems posed to experienced architects, showed that the problem was twofold. First, almost without exception, architects were routinely mapping concurrent and structural hardware constructs to an unnatural procedural (object-oriented or not) and sequential form bearing little resemblance to the original hardware. This unnecessary, tedious, and often error prone manual mapping process caused what is now known as the mapping problem. [TOCS 2005, MICRO 2002] Second, while the mapping problem directly explained many of the ill effects architects were facing (primarily those of model correctness and expression), only the lack of component reuse could explain the remaining ill effects (chiefly the overhead of model development and the incomparability of models). This lack of reuse results from the improper factorization of components, yielding components only able to operate correctly within the context for which they were developed. A particularly problematic aspect of this factorization comes from modeling the inherently monolithic centralized control in hardware. [TOCS 2005, MICRO 2002]

With an understanding of the problem, we developed a tool called the Liberty Simulation Environment (LSE) in order to embody the proposed solutions and to measure their impact. The success of LSE has inspired an international standardization effort called The Unisim Project. [CAL 2007] The Unisim Project continues under the skillful leadership of Prof. Olivier Temam of INRIA.

The Liberty Simulation Environment (LSE)

To address the mapping problem, LSE provides a language designed for the direct expression of hardware constructs. [PLDI 2004] This language, called the Liberty Structural Specification Language (LSS), is similar in concept to hardware synthesis languages such as Verilog and SystemC, but it supports abstractions most interesting to computer architects. To address the problem of centralized control, LSE introduces the notion of a control abstraction. [TOCS 2005, MICRO 2002] In breaking with the way in which hardware control is manually defined for each machine configuration, LSE's control abstraction allows a decentralized control specification to achieve equivalent behavior automatically for each configuration. Interestingly, as the complexity of hardware design increases, many processor designers are now adopting a latency insensitive design approach that very closely resembles our earlier control abstraction work.

To encourage component reuse, we developed new programming language concepts to support static inference based on the hardware structure and to achieve flexibility via parameterizable structure. [PLDI 2004] To support these concepts, LSS introduced a new type system that can handle both component overloading and parametric polymorphism of architectural components. Though type inference for languages with this property is NP-complete, we devised a heuristic type inference algorithm that works efficiently in practice. [ISSS 2004] LSS also introduced a new programming language technique, called use-based specialization, which, in a manner analogous to type inference, customizes reusable components by statically inferring structural properties that otherwise would have had to have been specified manually. [PLDI 2004, TOCS 2005] Already, many of these language concepts have been adopted by developers of modeling tools working in collaboration with us and independently. [MEJ 2002, SASIMI 2001, EMSOFT 2002]

To date, we have released four major versions of LSE, each incorporating extensive feedback from researchers at the University of California at Berkeley, Rice University, Harvard University, INRIA, and the University of Michigan. Early versions were used successfully in the Justice Project at the University of Illinois, in the Itanium Project at Universitat Politècnica De Catalunya, in the ORION project in Princeton's Electrical Engineering Department, and in coursework (at the University of Colorado, the University of California at Berkeley, and Princeton University). ["Orion: a power-performance simulator for interconnection networks", H.-S. Wang, L.-S. Peh, S. Malik, MICRO 2002, "A power model for routers: modeling Alpha 21364 and InfiniBand routers", H.-S. Wang, L.-S. Peh, S. Malik, IEEE Micro, WCAE 2003] LSE version 1.0, released in 2004, combines a variety of novel simulation techniques. [PER 2004, HPCA 2006, DAC 2003, IJPP 2005] Users of LSE see dramatic improvements over prior methodologies. A single student in our group developed an Itanium 2 processor model in 11 weeks (including time necessary to reverse engineer the Itanium 2 processor itself) that is accurate to within 5% of actual hardware for the SPEC 2000 benchmarks. [MoBS 2005]. Over 80% of the components used in this model were reused from generic models developed earlier. This compares extremely favorably to typical processor model development, which is measured in person-years (not person-weeks), where an accuracy of within 20% is considered very good, and where often nothing is reused. Similar success using LSE has been published by others in the development of an extremely accurate (again within 5%), validated multi-core network interface controller (TIGON-2) model developed in 2 person-months (The Rice University SPINACH project). ["Spinach: A Liberty-based Simulator for Programmable Network Interface Architectures", P. Willmann, M. Brogioli, and V. S. Pai, LCTES 2004] Users of LSE attribute the rapid and accurate model development mainly to easy reuse and to the elimination of the mapping problem, and they attribute the high levels of reuse obtained to the proper control abstractions.

Unisim

Working with prominent researchers in the US and Europe, we helped establish an international standard for the interoperability of simulation model components based on our contributions to modeling methodology. This effort, called the Unisim Project, adopts key concepts from LSE. The Unisim Project addresses the problem of adoption for those with large investments in existing models by providing efficient adaptors, a research challenge given the diversity of models of computation currently in use. Already, the HiPEAC network (a group of over 70 European computer architecture research groups), several companies, and leaders in modeling research (including researchers at INRIA, Carnegie-Mellon University, the University of California at San Diego, the University of Michigan, and the University of Colorado) have agreed to adopt, to promote, and to contribute to the development of this standard. As adoption increases, we expect the high degree of reuse and interoperability achieved to accelerate architectural innovation, eliminate recurring costs, and reduce the barrier to entry for novel computer architecture exploration.

Project Ph.D. Graduates

Selected Project Publications

All Project Publications

Structural Simulation for Architecture Exploration
David I. August, Veerle Desmet, Silvain Girbal, Daniel Gracia Pérez, and Olivier Temam
Processor and System-on-Chip Simulation (ISBN: 978-1441961747)
Edited by Rainer Leupers and Olivier Temam. Springer, September 2010.

UNISIM: An Open Simulation Environment and Library for Complex Architecture Design and Collaborative Development [abstract] (IEEE Xplore, PDF)
David I. August, Jonathan Chang, Sylvain Girbal, Daniel Gracia-Perez, Gilles Mouchard, David Penry, Olivier Temam, and Neil Vachharajani
IEEE Computer Architecture Letters (CAL), September 2007.

The Acceleration of Structural Microarchitectural Simulation via Scheduling [abstract] (PDF)
David A. Penry
Ph.D. Thesis, Department of Computer Science, Princeton University, November 2006.

The Liberty Simulation Environment: A Deliberate Approach to High-Level System Modeling [abstract] (ACM DL, PDF)
Manish Vachharajani, Neil Vachharajani, David A. Penry, Jason A. Blome, Sharad Malik, and David I. August
ACM Transactions on Computer Systems (TOCS), Volume 24, Number 3, August 2006.
Accept Rate: 16%

Exploiting Parallelism and Structure to Accelerate the Simulation of Chip Multi-processors [abstract] (IEEE Xplore, PDF)
David A. Penry, Daniel Fay, David Hodgdon, Ryan Wells, Graham Schelle, David I. August, and Daniel A. Connors
Proceedings of the Twelfth International Symposium on High-Performance Computer Architecture (HPCA), February 2006.
Accept Rate: 15% (26/172).

Achieving Structural and Composable Modeling of Complex Systems [abstract] (SpringerLink, PDF)
David I. August, Sharad Malik, Li-Shiuan Peh, Vijay Pai, Manish Vachharajani, and Paul Willmann
The International Journal of Parallel Programming (IJPP), Volume 33, June 2005. Invited.

Rapid Development of Flexible Validated Processor Models [abstract] (PDF)
David A. Penry, Manish Vachharajani, and David I. August
Proceedings of the Workshop on Modeling, Benchmarking, and Simulation (MoBS), June 2005.
Accept Rate: 45% (10/22).

Rapid Development of Flexible Validated Processor Models [abstract] (PDF)
David A. Penry, Manish Vachharajani, and David I. August
Liberty Research Group Technical Report 04-03, November 2004.

Microarchitecture Modeling for Design-space Exploration [abstract] (PDF)
Manish Vachharajani
Ph.D. Thesis, Department of Electrical Engineering, Princeton University, November 2004.

Facilitating Reuse in Hardware Models with Enhanced Type Inference [abstract] (ACM DL, PDF)
Manish Vachharajani, Neil Vachharajani, Sharad Malik, and David I. August
The IEEE/ACM/IFIP Second International Conference on Hardware/Software Codesign and System Synthesis (ISSS), September 2004.
Accept Rate: 24% (39/159).

The Liberty Structural Specification Language: A High-Level Modeling Language for Component Reuse [abstract] (ACM DL, PDF)
Manish Vachharajani, Neil Vachharajani, and David I. August
Proceedings of the 2004 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2004.
Accept Rate: 19% (25/128).

The Liberty Simulation Environment, Version 1.0 [abstract] (ACM DL, PDF)
Manish Vachharajani, Neil Vachharajani, David A. Penry, Jason Blome, and David I. August
Performance Evaluation Review: Special Issue on Tools for Architecture Research (PER), Volume 31, Number 4, March 2004. Invited.

The Liberty Simulation Environment: A Deliberate Approach to High-Level System Modeling [abstract] (PDF)
Manish Vachharajani, Neil Vachharajani, David A. Penry, Jason A. Blome, Sharad Malik, and David I. August
Liberty Research Group Technical Report 04-02, March 2004.

A Study of the Clarity of Functionally and Structurally Composed High-level Simulation Models (PDF)
Manish Vachharajani and David I. August
Liberty Research Group Technical Report 04-01, January 2004.

Liberty Simulation Environment, Version 1.0
Manish Vachharajani, David A. Penry, Neil Vachharajani, Jason A. Blome, and David I. August
Available at http://liberty.princeton.edu/Software/LSE, December 2003.

A Comparison of Reuse in Object-oriented Programming and Structural Modeling Systems [abstract] (PDF)
Manish Vachharajani, Neil Vachharajani, and David I. August
Liberty Research Group Technical Report 03-01, October 2003.

Challenges in Computer Architecture Evaluation [abstract] (IEEE Xplore, PDF, PostScript)
Kevin Skadron, Margaret Martonosi, David I. August, Mark D. Hill, David J. Lilja, and Vijay S. Pai
IEEE Computer, August 2003.

The Liberty Simulation Environment as a Pedagogical Tool [abstract] (PDF)
Jason Blome, Manish Vachharajani, Neil Vachharajani, and David I. August
Proceedings of the Workshop on Computer Architecture Education (WCAE), June 2003.

Optimizations for a Simulator Construction System Supporting Reusable Components [abstract] (ACM DL, PDF)
David A. Penry and David I. August
Proceedings of the 40th Design Automation Conference (DAC), June 2003.
Accept Rate: 24% (152/628).

Microarchitectural Exploration with Liberty [abstract] (IEEE Xplore, PDF)
Manish Vachharajani, Neil Vachharajani, David A. Penry, Jason A. Blome, and David I. August
Proceedings of the 35th International Symposium on Microarchitecture (MICRO), November 2002.
Accept Rate: 24% (36/150).
Winner Best Student Paper Award.

A Disciplined Approach to the Development of Platform Architectures [abstract] (CiteSeerX, PDF)
David I. August, Kurt Keutzer, Sharad Malik, and A. Richard Newton
Microelectronics Journal, Volume 33, Number 11, November 2002. Invited.

Design Tools for Application Specific Embedded Processors [abstract] (SpringerLink, PDF)
Wei Qin, Subramanian Rajagopalan, Manish Vachharajani, Hangsheng Wang, Xinping Zhu, David I. August, Kurt Keutzer, Sharad Malik, and Li-Shiuan Peh
Proceedings of the Second International Workshop on Embedded Software, Lecture Notes in Computer Science (EMSOFT), Volume 2491, October 2002. Invited.

A Disciplined Approach to the Development of Platform Architectures [abstract] (PDF)
David I. August, Kurt Keutzer, Sharad Malik, and A. Richard Newton
Proceedings of the Tenth Workshop on Synthesis and System Integration of Mixed Technologies (SASIMI), April 2001. Invited.