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

302 Found

Found

The document has moved here.