Below are descriptions of suitable course projects. With additional work, some of these projects can lead to a publication in a conference, and/or PhD dissertation research. In some cases, support in the form of a graduate research assistantship for continuing work this summer may be possible.

Each project includes two checkpoints where a specific deliverable is due, and the final report. Weekly meetings will be arranged through the remainder of the semester to maintain progress in the projects and to provide feedback. An oral presentation is also required at the end of the semester describing the problem you worked on, and results that are available at the time of the report.

Due dates are as follows:

• Project selection: Friday, March 17
• First Checkpoint: Friday, March 31
• Second Checkpoint: Friday, April 14
• Final Report: 5 PM, Tuesday, May 2 (turn in to Jennifer Chisholm in room 264 CCB).

If you are doing a project from the following list, simply turn in a sheet of paper indicating which project you will work on for the project selection due date (note some additional information is required if you are doing the virtual environment project, however). You are free to propose your own project. If you plan to define your own project you should see me first to discuss what you want to do. In this case, the project selection write up should describe your project in detail comparable to the project descriptions that follow. Be sure to indicate what milestones you will reach at each of the checkpoints, as well as the final report.

All projects listed below are intended for one person, unless indicated otherwise. Persons taking this course for undergraduate credit may complete any of the projects listed below. Persons taking this course for graduate credit may complete any except the Virtual Environment project.

More than one person may select the same project to work on. You may (and in fact are encouraged) to discuss how you will approach the project with other persons working on the same project, but all code and reports that you turn in must be entirely your own work.

Most of the projects that follow will require making some significant modifications to the FDK software, or another software package called GTW/TeD. We will provide help and suggestions on how to modify this software to complete the project, but keep in mind these are research oriented projects, so complete solutions have not been worked out.

The goal of this project is to realize an efficient implementation of the FDK software that runs over a collection of shared memory multiprocessors interconnected via Myrinet switches. Communications between processors residing within the same SMP should use a shared memory message passing mechanism. This software is already available for the SGI multiprocessor; you will need to port it to the PC SMP cluster for use in this project. Communication between processors residing in different SMPs should use Myrinet message passing software, using a software package called GM. Myrinet is a high speed switch that enables low latency communication by bypassing the software protocol stack used in traditional networks. The native Myrinet hardware can provide communication latency on the order of a few microseconds when sending small messages, compared to hundreds of microseconds for traditional local area networks. You will use a cluster of PC-based SMPs interconnected with Myrinet hardware for this project.

There are two parts to this project. The first is porting the existing SMP implementation of FDK to execute on a single PC SMP. The second, which forms the main portion of the project, requires extending this implementation to include fast communications via the Myrinet for communication between processes mapped to different SMPs. This requires extending the communication software used by FDK (called FM-lib) to support inter-SMP communication. This should all be transparent to higher level software (specifically the rest of the RTI software and federates interconnected by the RTI).

Achieving high performance is a central focus of this project. It is important that your design minimize software overheads, e.g., message copying.

You must complete the following tasks for this project:

• Checkpoint 1: Port the existing SMP implementation to execute on a single PC SMP. To complete this checkpoint, you should be able to run standard FDK benchmarks on the SMP.
• Checkpoint 2: come up with design for the multi-SMP implementation. You will need to familiarize yourself with the GM message passing API used for communication over Myrinet. Write a simple test program for this purpose. Come up with a design to build the FM communication layer used by FDK that operates over the SMP/Myrinet communication software.
• Final report: You should have an operational implementation of FDK executing over the multi-SMP environment. Measure communication latency and bandwidth for communication between processors within the same SMP, and between different SMPs for different message payload sizes, both for processes directly using your software at the FM API, as well as that for federates executing over the RTI. Compare this with performance using TCP messages using Ethernet.

Suggested Reading:

Communication protocols such as TCP/IP executing over local or wide area networks are more efficient in sending large messages than small ones. Applications such as discrete event simulations tend to send many small messages. Such applications are often more efficiently implemented by using a technique called message bundling where several outgoing messages for a specific destination are buffered, and then sent over the network as a single large message rather than several smaller messages. The goal of this project is to implement message bundling in FDK, and to evaluate its performance relative to the current implementation that does not use message bundling.

This project requires the completion of the following tasks:

• First checkpoint: Design a message bundling scheme, and describe how you will embed it into the FDK software. The bundling software you add will most likely be added to the FM-lib communication layer, making it available for all of the RTI software using these services. You should do a literature survey describing some schemes for bundling others have proposed.
• Second checkpoint: You should have an initial implementation of the bundling software ready by this checkpoint. Update your documentation indicating any modifications that were made to the design, and discuss your experiences in implementing the scheme.
• Final report: You should complete a thorough performance evaluation of your bundling software implementation. Construct both synthetic workloads designed to show where bundling will provide maximal performance advantage, as well as workloads where it provides no advantage, or may even perform worse than the non-bundled implementation. Include some existing simulations (e.g., the tank simulation used in the homework) as benchmarks to evaluate the effectiveness of bundling and to assess its impact on performance.

Suggested Reading:

The current FDK software uses a single threaded approach where each federate must explicitly call the tick() procedure to give the RTI cycles to perform tasks such as receiving messages and to perform time management computations. This project will explore an alternate approach where federates need not call tick(), but rather a separate thread executes on each processor that performs this function. To complete this project you must come up with a design to transform the single-threaded FDK software to a multi-threaded version, implement your design, and perform a thorough performance evaluation study.

This project requires completion of the following tasks:

• First checkpoint: Come up with a design for the multi-threaded architecture. You will need to understand the overall structure and flow of control in the current, single-threaded implementation of the FDK software, as well as the primitives for controlling the execution of threads in the multi-threaded implementation. Your design should include some tuning parameters to control when the RTI thread executes.
• Second checkpoint: At least a partial implementation of the multi-threaded version should be operational for the second checkpoint. Turn in a revised version of the write up for the first check point indicating any design changes, and a status report on what portions are operational.
• Final report: Complete a thorough performance evaluation study to evaluate the overheads of the multi-threaded version and the performance of this implementation relative to the original single-threaded version. You will need to design some interesting benchmark programs to identify situations where the multithreaded version should perform well, and situations where the single threaded version should perform well. You should consider both basic communication benchmark programs as well as applications using the time management software.

Suggested Reading:

The goal of this project is to realize an alternate implementation of FDK's time management software (TM-Kit). Specifically, the current FDK software computes LBTS values (a lower bound on the time stamp of future messages a processor can receive), but does not take into consideration topology information, i.e., information concerning which federates communicate with which other federates. This project involves developing a replacement that takes into account topology information, and an evaluation to determine its effect on performance.

To simplify the implementation of this mechanism, you should try to preserve the existing interface to the time management software as much as possible. You will need to add some additional information (e.g., topology information) however. In principle, one can deduce topology information from the publications and subscriptions made by each federate. To simplify this project, however, you may use a separate mechanism, e.g., a configuration file of your own design to provide topology information. Assume a separate lookahead value is associated with each link in the topology, and the topology and lookahead values do not change during the execution of the simulation.

• Checkpoint 1: Complete a design of the time management software and its implementation in sufficient detail for us to evaluate problems that may come up. Describe both the algorithm and how you will embed it into FDK (i.e., what changes to the other FDK software other than TM-Kit will need to be changed). Document the interface to your software and if you are using special files, the format of these files.
• Checkpoint 2: Develop an initial implementation of the time management software that is able to correctly compute LBTS values for each federate. Use the FM-lib communication software to realize interprocessor communication. Aim for an implementation of your time management algorithm over FM-lib for this checkpoint, with a simple program used to initiate LBTS computations. In the final phase of this project you will bring up one of FDK's RTI implementations over your time management software.
• Final Report: Embed your time management implementation into one of FDK's RTIs. D-RTI is recommended for this purpose. A series of experiments must be developed to evaluate situations where the new algorithm improves performance and situations where it does not. You will need to hypothesize when it should improve things and when it doesn't, and construct a series of experiments to test your hypotheses. The final report should document your findings and explain any unexpected results.

Suggested Reading:

Many of the techniques used in optimistic synchronization of distributed simulations are also applicable to fault tolerant system design. In particular, it is well known that optimistic synchronization can be used to recover from failures in distributed systems. Specifically, detecting a failure can be used to trigger a Time Warp like rollback mechanism to return the distributed system to a consistent state. The state of the system is checkpointed (to secondary storage) to enable recovery from failures.

While one can directly apply Time Warp like mechanisms to implement distributed failure recovery, a problem is the associated overhead which involves disk I/O to retrieve a checkpointed state of each process being rolled back. This overhead can be reduced by recomputing rather than checkpointing a prior state of the system. In prior work, we have developed a way to automatically generate the reverse computation of segments of code in order to recompute prior states of the system.

This project involves (1) developing an algorithm for distributed failure recovery using the reverse computation mechanism, and (2) adding modifications to our existing reverse execution Time Warp system to partially implement the failure recovery mechanism. Specifically, you will modify an operational Time Warp system based on reverse computation to add disk I/O to checkpoint state and message logs. Note that this project does not use the FDK software, but rather a different package called Georgia Tech Time Warp (GTW).

To complete this project, you must perform the following tasks:

• First checkpoint: a paper design of the failure recovery protocol using reverse computation must be developed. You will also need to review some relevant background literature in this area. Specifically, you should read papers on Time Warp using reverse computation, and one or more papers on optimistic failure recovery (references will be provided).
• Second checkpoint: An initial design of the failure recovery mechanism that will be implemented in the GTW software (using reverse computation) must be developed. Specifically, you will need to describe how you intend to add checkpointing (to disk) and message logging (also to disk) software, as well as the necessary recovery procedures. It would be useful if you had some initial implementation work done at this point also.
• Final report: The goal is to have an operational prototype running by the end of the semester. Time permitting, some preliminary performance measurements of the implementation would also be useful. The final report should describe both the failure recovery mechanism, the implementation, and experiences you encountered in implementing the mechanism.

Professor Doug Blough (ECE) and Dr. Kalyan Perumalla will participate in this project. Professor Blough is an expert in fault tolerant computing, and Dr. Perumalla is an expert in reverse computation, and developed the reverse computation software you will modify for use in this project.

Suggested Reading:

C. D. Carothers, K. S. Perumalla, R. M. Fujimoto, "Efficient Optimistic Parallel Simulation Using Reverse Computation," 13th Workshop on Parallel and Distributed Simulation, 1999 pp. 126-135.

This project is only for those taking the course for undergraduate credit. It involves building a distributed simulation application on top of the FDK software. The goal of this project is to realize an interactive distributed simulation application (e.g., a multi-player video game) over FDK. You are free to choose the type of game to be implemented. A "first-person" viewer application is preferable where the display seen by each user is that which would be seen by a person embedded within the virtual environment. In addition to the interactive participants in the virtual environment, there should be simulated entities moving throughout the virtual world, e.g., simulated adversaries.

A software package called Crystal is available for use in this project that provides support for creating virtual environments. It is recommended you use Crystal or a similar package rather than attempt to build everything from scratch.

This project can be done individually or in teams. One approach for a team project is to have each person build a different type of entity that is embedded in the virtual environment.

The tasks for this project include:

• Project selection: Give a brief (a paragraph of two) description of the virtual environment you hope to create for the course project.
• First checkpoint: You should come up with a specification of what will be included in the virtual environment, and describe how you plan to implement it. A description of the virtual environment from the perspective of a user should be documented. An initial (possibly throw away) program using Crystal (or the software package you intend to use) should be implemented to familiarize yourself with this package, and how it can be interfaced with the FDK software.
• Second checkpoint: An initial, version of the virtual environment demonstrating some (albeit perhaps limited) capability should be developed that can be used as a base for completion of the project.
• Final report: The virtual environment should be completed, and a demo presented showing the pieces you were able to get working.