Traps, Interrupts, and Exceptions in GEMS

Today, someone asked on the gems-users mailing list the question, "How does GEMS simulate traps?" I gave my best answer, and the topic is a good prelude to an upcoming post I'm planning.

GEMS is a computer hardware simulator, and I have discussed it previously. Simics/GEMS is primarily a three-headed monster: Simics, Opal, and Ruby. Simics+Opal implement the processor simulator, and Ruby implements the memory hierarchy for multicore platforms. My work primarily uses Simics+Opal, without Ruby.  Opal is a "timing-first" simulator based on TFsim. It implements most of the processor model, but relies on the functional simulator (Simics) to verify simulation correctness and to provide some of the harder-to-model processor features.

One of the harder-to-model features of modern processors is the exception/interrupt handling mechanism. In the SPARC-v9 architecture, these are both referred to as traps. Opal models trap handling for a subset of the possible traps, including register window traps, TLB misses, and software interrupts. All trap handling is done in the retire stage of the instruction window, which allows speculation past traps. Non-modelled traps in Opal, for example I/O, rely on Simics to provide the functional implementation of taking the trap and updating the architected state. Modelled traps simulate the trap handling algorithms and should result in the same architected state as functionally correct trap handling.

Modelled traps improve simulation accuracy. In-flight instructions are squashed, the program counter (and other register state) is properly updated, and Opal continues to execute the workload. Simulator correctness depends on the ability of Opal to generate the same traps as Simics, and simulator accuracy requires Opal to model the effects of taking the trap.

That's all for now. In the near future, I will be expanding on this topic to discuss how to add new traps to Simics/GEMS.

Information Warfare

I had the pleasure of helping out at the 6th International Conference on Information Warfare and Security (ICIW 2011) and enjoyed re-engaging my brain's security neurons. This year's ICIW was quite diverse, with a large number of countries represented and participation from both academia and government. All in all, I thought it was a great conference on information operations.

Although not my core area of research, information operations (or "warfare") is an area of applied computer security that also includes aspects of societal studies and psychological disciplines. In truth, information warfare is legitimized (state sponsored) hacking.

Something that struck me was that the US appears to be lagging behind some other countries with respect to organizing and training information operators. It is widely believed that China has a hierarchy of hackers organized somehow within its armed forces or governmental regime.  I also learned that Estonia has a volunteer "cyber militia", which I guess would be something like Minutemen hackers.

I know that various US government branches recruit students with technical skills, primarily via scholarship for service programs. I'm also given to understand that armed forces assign personnel to information operations work, but I think this is mainly in using regular IT infrastructure. The technically challenging work is relegated to contracting firms, who may employ white/gray-hat hackers as penetration testers and similar.

I don't believe much work is done in engaging the hobbyists and those with technical hacking abilities but without formal technical education beyond high school. In fact, it is hinted that many talented individuals end up in the black-hat community simply because they lack higher education.

Given the untapped talent pool out there, I wonder if the future holds the possibility for cyber-militia (a la the National Guard) and a new branch of armed forces aimed directly at recruiting and training cyber-infantry?  If the current trends in information warfare continue, it seems likely that such skills will be required. They would also be transferable to the private sector, which I think is an interesting thought to ponder.

The Future (?) of Computing

Making predictions is a questionable exercise at best. However, it is important to look forward and try to see what is coming down the road. So I'm going to give my perspective on where I think the (electronic) computing industry is headed, along with an overview of where it has been.

the past
The computing industry as we know it was born out of the government and academic projects that sought to improve on the ENIAC machine by enabling stored program computing. The EDSAC project showed that a stored program computer is possible, and its complex control logic motivated the microprogrammable control unit.  Many subsequent developments in computer architecture can be traced back to the philosophy and goals of microprogramming:

• Reduce the complexity of control. Regular hardware structures, interconnects, and single-cycle microinstructions are paralleled in the development of RISC architectures and modern CMP (multicore) designs.
• Improve programmer productivity. The microprogrammed control store translates assembly (the dominant language of the 50s and 60s) into sequences of machine operations. This translation mechanism leads to increased use of complex instructions and resultant CISC architectures.
• Compatibility across machine generations. By implementing a language interpreter in microcode, an assembly language can stay fixed while the underlying machine changes. Binary compatibility and bitslicing result from interpreted assembly and lead to ISA families. This use of microprogramming can still be seen in the Intel x86 architecture.
• Extract hardware parallelism.
  New hardware resources can be used in parallel by packing more operations in (wider) microinstructions, known as horizontal microprogramming. The technique of issuing multiple parallel instructions leads to VLIW architectures.  VLIW research drove compiler technology, because the compiler is responsible for determining the parallel instructions to pack in a VLIW instruction word. Intel brought VLIW to market with the Itaniam, the IA-64 ISA, but that has not seen very much success.

Technological innovations in materials (such as silicon integrated circuits) pushed the industry forward at exponential rates.  Materials, namely transistors, became cheaper, driving computing costs down and lowering the barrier to entry for academic and commercial computing.  Concurrent to the improvement in materials came more ways to use computers, driven by advances in programming methods and networking.  The software crisis was understood and spawned research in languages and software engineering. The ARPANET/Internet was developed. Computers became cheaper, faster, connected, and more useful.

the present
In 1995, the memory wall was identified as the performance bottleneck caused by processing speed improving faster than off-chip peripheral performance, especially that of memory. It seemed that the "free lunch" of faster software due to better hardware would go away. However, computer architects brought to market techniques that mitigate memory access latencies: out-of-order (OoO) execution, caching, prefetching, and simultaneous multithreading (SMT). These are reasonably well-explained on wikipedia, although no replacement for an authoritative source, such as Hennessy and Patterson.

In the 2000s, the power wall (see Hennessy and Patterson, 2009) results directly from packing more transistors into chips. Enter the multicore. By using simpler pipelines in parallel, computer architects can keep clock frequencies and feature density low while utilizing the available transistors. The main approach to exploit parallelism is the chip multiprocessor (CMP), also called the multicore microprocessor or simply multicore. Intel, AMD, Sun Microsystems, IBM, and others have brought multicore computing to the public, and the paradigm seems poised to continue for at least the next generation of processor families.

the future
My opinion is that, barring unforeseen technology, the multicore era may herald the end of the "general purpose processor." If (when) the cloud computing paradigm catches on, the need for powerful desktops will be reduced and, therefore, the market factors that drive powerful general purpose processors will decline.  Special-purpose processors will appear that serve niche markets.  Already this is seen in the form of GPGPU-CPU hybrids, which serve the substantial videogaming and streaming video markets. Because not all application spaces can benefit from SIMD parallelism, other special-purpose hardware will appear.

My belief is that special-purpose hardware will take some form of (re)configurable logic, such as FPGA, CGRA, or an as-yet-unknown technology. The performance gaps of current reconfigurable hardware to application specific integrated circuits (ASICs) will be less impactful on future applications in conjunction with the shift toward cloud computing. Furthermore, integrating reconfigurable logic with hard-wired functionality such as processor cores, e.g. http://www.eetimes.com/electronics-news/4210937/Intel-rolls-six-merged-Atom-FPGA-chips, further reduces the power and performance gaps.  I'm not convinced FPGAs are the solution, but I think something similar will become the "general purpose processor" of the future, or at least will have the dominant market share for (non-embedded) end use.

I think the industry will continue to move forward in four broad directions: power-conscious servers, performance-hungry desktop users, embedded devices, and thin clients.  Servers are likely to continue using the multicore model, since they benefit greatly from thread-level parallelism. Compute-heavy desktops are likely to adapt the multicore and GPGPU models, while also relying on the ability to compose cores for better single processor performance for applications that do not benefit from either thread-level or SIMD parallelism. Ever smaller, power-conscious platforms will enable processor-based computation in more everyday items, driving the development of concepts such as smart homes.  Finally, thin clients will continue to evolve, from the mobile platforms such as smartphones and tablet computers to the next generation "cloud clients."  Such clients will benefit from simple low-power processing cores and flexible hardware that can adapt to the specific workload of the client.

I believe the processor architectures of the future will be divergent, and there will be a variety of computer architecture families. Advances in multicore computing will improve servers and compute-heavy desktops. Single processor performance will continue to be important, especially in embedded and thin client markets, but also in compute-heavy desktops. Power will remain an important factor for all processors, but the programming tools to support the variety of processing models will be as important.  Uniprocessor programming is pretty well understood, but programming parallel and reconfigurable computers remains hard.

The challenge for computer architects will continue to be to design platforms for servers, desktops, embedded systems, or thin clients that provide (1) appropriate performance, (2) power-consciousness, and (3) support for programmer abstractions.

OT: Apple Pie

The holidays really give me a hankering for pie.  I made some apple pies awhile back after going apple picking, and I took a couple photos.

Although there is no more pie to share, I can share some of the photos and my apple pie recipe.  Just click through the jump for some apple pie goodness.

RTEMS: Adding a new scheduler

In this post I describe how to add a new scheduler implementation to the RTEMS open-source real-time operating system. The scheduler I use as an example is an earliest deadline first (EDF) scheduler which applies the EDF algorithm to schedule periodic tasks and a FIFO policy for non-periodic tasks.  This post demonstrates how to use my modular scheduling framework to extend the scheduling capabilities of RTEMS.

Architectural simulators

As a researcher in the areas of operating systems, compilers, and computer architecture, I spend a lot of time dealing with simulators.  An inordinate amount of time.  Much of this time is spent figuring out how well a given simulator provides:

1. Useful timing measurements (cycle-accurate)
2. Support for fully functional OSs (full-system)
3. Auxiliary features for specific experiments
4. Support for useful hardware platforms and instruction sets
5. Openness to modifying microarchitectural features
6. Availability of technical support

In my current work, I'm interested in actively developed simulators that support cycle-accurate full-system simulation with a detailed memory hierarchy on out-of-order uniprocessor or multicore RISC architecture models with the SPARC, MIPS, or ARM instruction sets that supports extending the pipeline and instruction set.  The rest of this article discussed my efforts in finding simulators to meet my needs.

Interrupt Handling with MMU Hardware on an MMU-less OS

This post describes some work that I have just recently gotten to a point that it seems to be correct.  It was a long-running project that started around May 2010.