When to make thesis slides

I've been working on my thesis proposal for awhile now, and I even took one attempt at writing it which turned out to be a bit premature. My advisor suggested that I consider making my proposal defense slides before I write the proposal. I have now finished my first iteration on the slides and found it to be a most useful exercise. The content of my slides covers what I plan to address in my proposal, although the presentation needs a unifying story to tie everything together. A presentation should have a strong motivation and story because it is important to hook the audience in the first couple of slides and to keep them engaged throughout.

My feeling is that if I start by writing my proposal, I would have a sub-par narrative that would be weak when translated to a presentation. I usually start writing with an outline, then I fill in the technical details, results, and conclusion, then write the background material: introduction, motivation, and related work.  Making the presentation slides first will allow me to follow a single story throughout the proposal.

The act of thinking about how to present my work makes me consider more deeply both the organization and narrative than when I sit down to write. By expending more energy on the why and less the how, I can focus on a narrative that puts my proposed work in context and motivates my contribution. After I finish my slides, I will write my proposal using the slides as a guideline. This approach should yield a concise, readable proposal with a flow that is consistent with the presentation.

I also expect that most of my slides will be reusable for the thesis defense (and potential job talks), since the motivation and high-level ideas will be largely unchanged. Although some details and results will change, these will amount to a small delta in the presentation that will be easy to update.

Evaluating Research by Squeezing

John Regehr writes about squeezing a research idea, an exercise for evaluating a research idea. A squeeze is like a feasibility study. An idea can also be squeezed after the fact to determine its value or identify future work for improvements. The basic idea is to find a bound on the performance improvement of the research idea.

To squeeze an idea you ask:

1. How much of the benefit can be attained without the new idea? 
2. If the new idea succeeds wildly, how much benefit can be attained?
3. How large is the gap between these two?

A good baseline, or control in more classical terms, yields the first step of a squeeze. Baseline results should represent state-of-the-art solutions that are readily available. Comparing a proposed idea to an in-house or contrived baseline often does not make for good science.

My experience has been that the second step is best accomplished by developing a model that stresses the enhancement proposed in the research idea. Exploring system behavior in the limit puts the proposed enhancement in perspective. Upper bounds on the usefulness of the idea can be determined by idealizing constraint parameters of the model. See applications of Amdahl's law for some examples of doing this right.

A metric that is easy to measure, explain, and visualize should be applied to the baseline and enhanced system. A good metric for evaluating a squeeze will also be useful in presenting results and selling the research project. The measures taken of the two systems provide the last step of the squeeze.

In systems work, this analysis is often seen when results are normalized to a baseline, such as a benchmark on a stock system. Typical metrics in final results include speedup, throughput (bandwidth), and latency. Casting a squeeze in similar language as final results eases transitioning from pilot studies to experiments to disseminating results.

Squeezing an idea is a way to determine if going forward with it makes sense. The results of the squeeze will be useful in motivating the contribution of the research idea. Gaps between experimental results and predicted upper bounds will provide areas for further improvement.

RTEMS GSoC 2011

Congratulations to the students accepted to participate in the GSoC 2011 with RTEMS as their mentoring organization!

Student: Christophe Huriaux
Project: Implementation of the ISO9660 filesystem
Goal: Implement the ISO9660 filesystem so that RTEMS can read CD, DVD, and similar media.

Student: Ricardo Aguirre Reyes
Project: POSIX Timing Tests
Goal: Implement a suite of tests to time POSIX routines.

Student: Cui Xiang
Project: POSIX Compliance Test Suite (misnomer)
Goal: Implement a suite of tests for filesystem testing.

Student: Petr Benes
Project: Porting of resource reservation framework to RTEMS executive
Goal: Port the FRESCOR resource reservation framework to support RTEMS.

Student: Quanming Shi
Project: RTEMS MMU Context Support
Goal: Implement an architecture independent API and structure to manage memory blocks with access attributes based on MMU Support.

Student: Scotty Smith
Project: Lua Scripting and Shell Support in RTEMS
Goal: Add Lua as a library in RTEMS and provide a Lua-based shell as an alternate to the current shell.

Student: Zhang Wenjie
Project: Hypervisor for RTEMS
Goal: Implement virtualization support in RTEMS kernel and demonstrate Linux running on RTEMS.

Student: Jie Liu
Project: RTEMS port of the GNU Java Compiler
Goal: Support compiling Java applications on RTEMS with the GCJ (for x86 at least).

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.