Projects | People | Courses | Funding
Implemented algorithms for nanocell optimization techniques. A nanocell is a product that can be programmed to function as any of a large range of standard logic gates. Along each edge of the nanocell, there are pins that can be classified as either input, output, or control pins. Our goal was to vary the voltage on these pins in order to find a more optimal solution to the nanocell problem. Once the internal switches have been set by the initial genetic algorithm, a second optimization can then be run (at lower voltages so as not to reset the internal switches) to find the desired value of the control pins.
In CPS 4, students build interactive graphical programs in Java from very early on in the course. This is possible because we use a high-level framework that simplifies the amount of set-up work students must do. Additionally, the framework provides a uniform object-oriented interface so the number of special cases students must learn is minimized. Robert Duvall is working to build an environment around this framework to make it easier for novice programmers to build, debug, experiment, and ultimately better understand the models they program. David Wang is working to extend this framework to make it easier for novice programmers to extend the types of programs they can write in their first semester.
Developed a framework for deploying and designing networked games, specifically multi-player games like Boggle and Bingo. This was to be a robust but simple framework for understanding network issues and distributed computing at a simple level. The framework they developed wasn't finalized and hasn't been used in our courses, but the work is continuing in summer 2001 and this framework is successful.
Worked on Lempel-Ziv and Dynamic Huffman coding, writing programs for these (and regular huffman) comparing the performance of different implementations and evaluating which worked well under different circumstances. They developed extensive experiments comparing different implementations. Code is written in both C++ and Java. Web pages describe the algorithms and implementation issues as well as the results of the experiments. The intent of this assignment is to augment our standard Huffman assignment (used in our CS2 course) with an assignment based on Lempel-Ziv. They also worked on C++ libraries for accessing data on webpages. This includes a client-simple library that works similarly to the java HTMLEditorKit library, but uses standard C and C++ in the back end to parse web pages. We used this library as the basis for a successful webpage/tag stack assignment in CPS 100 course (in fall/spring 2000,2001) Materials
Developed an alternative approach for learning computer science principles using gaming scenarios and techniques to build and visualize of computer code. This project is intended to be used as an educational aid independent of the course's lectures and labs that allows a novice student to practice programming at their own pace in a controlled environment.
Worked on assignments involving Java and database access. She installed mySQL, implemented JDBC code for an assignment based on database access and wrote up the assignment. This was intended for use in courses that don't emphasize database concepts, but in which familiarity with databases would be useful (e.g., our software design course).
Refactored a graphics/animation library called TOOGL for use on Unix and windows machines. This included a port from Windows to Unix using the QT-widget library [this port was not completed]. His work also entailed packaging the library for large scale distribution on windows platforms using Install shield.
Continued work on netlog started in previous summer.
(Jeff Chase, Landon Cox)
We are developing a simple framework for distributed Web-based applications in Java, both as a research infrastructure and as a basis for exercises in CPS 212, "Distributed Information Systems". Exercises in the first half of the semester will deal with basic Web infrastructure (HTTP servers, servlets for dynamic Web applications, and proxy caching) using TinyServer, a Java-based Web server with servlet support developed for the Fall 1998 offering of CPS 212. Exercises in the second half of the semester will deal with support for distributed information, including cache consistency, recoverable updates, distributed locking, distributed objects, and transactions.
The DROOL-supported work has extended TinyServer with support for proxy caching, Java Server Pages. More importantly, DROOL students have added support for shared, recoverable Java data structures and a sample application using shared graphical objects (i.e., a whiteboard). Geoff Berry's Pickles package (developed in the Summer of 1998) provides support for transferring data structures and updating them incrementally. In the Summer of 1999, Landon Cox integrated the Pickles package with TinyServer, added basic Web caching support, and added support for the server to propagate updates to caches or replicas.
Here's a brief outline of the exercises:
(Amin Vahdat, Garrett Mitchener)
This project developed networking assignments for CPS 214 in the fall 1999 semester. (and later for an undergraduate networkings course).
The material consists of three parts.
The first is a pair of network timing assignments that show the difference between bandwidth and latency and allow people to get some idea of the performance of a network.
The second is a chat room implemented four different ways: as clients and a server, as multicast clients, with password and secret key authentication, and with public key authentication. These are useful practice for writing clients and servers, learning about multicasting, and understanding Kerberos and other authentication protocols. The first and second parts are written in Java. The plan is to give people access to the sample solutions, and have them re-write all the major components. The advantage to having the sample solutions is that they can write and debug one piece at a time and still have a fully functional system.
The third part is a C++ low-level networking package called the Nano X Kernel (based on the X Kernel used in Mach). It's designed to be easier to understand and work with, plus be small enough to complile for the Lego robot kit. It includes several protocol layers from the hardware level on up. At the moment, there isn't any documentation for it other than the comments in the header files (which are pretty extensive) and a notes file. Our Lego people (Dan and Luis) should have very little trouble porting it to LegOS. It already runs on Solaris and should be trivial to port to Linux. (I think Solaris requires some extra libraries that Linux doesn't need, little things like that.) In the robotics class, they can use it to allow robots to communicate with each other and with more powerful computers. In 214, people will probably have to do end-of-course projects, and they'll have the option of doing something in C++ or Java based on NXK code. This assignment should be useful for learning how to work out the details of a communication protocol without getting into all the complexities of TCP and IP.
(Alvy Lebeck, Carl Mummert)
This work involved a port of the CProf system to Intel x86 machines running Windows NT. This system allows users to trace memory usage and generate cache miss statistics for their programs; this information allows the programmer to optimize the cache usage of a program to improve performance. As the gap between processor cycle time and memory fetch time increases, improving cache usage becomes correspondingly more important to good program performance.
Several similar tools have been written for RISC architectures, but the popular Intel processors have received less focus in research due to the complexity of their CISC machine code. The Cprof NT system gives programmers on common Windows NT machines a tool that was previously only available on high-end UNIX workstations.
(Susan Rodger, Ted Hung)
Modifications to tools JFLAP and Pate. Additions to JFLAP include adding in regular expressions, and increasing the interaction of users with JFLAP. Additions to Pate include visualization of a parse tree for unrestricted grammars and more interaction with the tool. Materials have been used in CPS 140 at Duke.
(Michael Littman, Anya Bilska)
CHARLEE (stoCHastic Animated Reinforcement Learning and Exploration Environment) is a program that simulates exploration, reinforcement learning, and optimal decision making in non-deterministic, two-dimensional environments (Markov decision processes). The environment is represented by a grid of locations, walls, and special cells containing punishments and rewards. The agent's task is to reach reward state while avoiding punishment states, while also minimizing the total cost of the journey. Probabilitistic transitions influence the course of the journey, making it take shorter or longer, depending on the outcome of movement events.
The user chooses the setup of the world to be explored: the grid size and shape, the location of walls, punishments and rewards, the step cost, and the probabilities associated with moving in each direction relative to the intended direction of motion. The program can be then used to calculate the optimal policy for reaching the reward locations with respect to the specified environment. Different exploration animations (based on the transition model probabilities) can be run and compared against the optimal one. Further work on the program will include allowing the agent to explore the environment by itself, the agent thus learning through trial and error, using reinforcement-learning algorithms.
The program will be used as a teaching tool to introduce topics in dynamic programming (CPS130) and reinforcement learning (CPS271). The class of environments implemented is based on classic examples in the field of reinforcement learning, and so students' experience with the program serves as a useful introduction to the research literature as well.
(Michael Littman, Paul Polo)
The problem is to calculate the utility and the optimal policy of each state in a given environment. The approach is to calculate a probability distribution over the possible states given all previous percepts, and to base decisions on this distribution. Calculating the utility of an action (policy), is made difficult by the fact that the actions will cause the agent to obtain new percepts, causing its beliefs to change in complex ways. The algorithms used for calculating optimal policies in this project are Value Iteration, Policy Iteration and Q-Learning.
(Jeff Chase, Philip Rash)
This project involved the following areas: GMS (Global Memory Service) logging, TCP (Transmission Control Protocol) logging, and Disk IO logging. GMS is a system for allowing nodes in a network cluster to share memory amongst one another. Logging allows one to see how GMS behaves. My primary contribution to GMS logging was some enhancement to the "log gatherer" program.
TCP logging was implemented to allow us to analyze the behavior of the TCP protocol as implemented over Trapeze. (Trapeze is a high-speed messaging facility; GMS is currently also implemented over Trapeze.) I both modified some already-existing TCP analysis tools and implemented a Java-based TCP illustrator that depicts segment traffic over time.
IO logging was my last endeavor of the summer. Here we log pertinent data when read/write requests are made to the disk device such as physical block number, size of transfer, device number, time, and stalls if they occur. This allows us to compute various statistics such as average stall time, average seek time, etc. We also were able to make various plots with this data such as physical block vs. time. This particular plot depicts action of the disk as requests are issued to it.
(Jeff Chase, Geoff Berry)
Ivory is an orthogonal logging and recovery infrastructure, implemented entirely in Java, which operates on Java programs. The package and its API are designed for simplicity and generality rather than as a full-featured transaction environment. Also, it is intended to support only ``small'' data structures that can reasonably be loaded in their entirety in the virtual machine. It was also designed to be used in concert with transformers which adapt applications to its API; however, this is not required, and the API can be usefully employed by any application.
The fundamental approach to implementing recoverability in Ivory is common to many other systems. The API provides primitives to take a checkpoint by writing out all reachable persistent objects; to mark an object as being dirty since the last checkpoint; and to commit a set of changes relative to the last checkpoint. The state of the application can then be recovered from these files on startup.
Ivory is going to be used as the basis for a course-long project (similar to Nachos) for the distributed systems class. The actual project will involve distributed graphical objects whose state will be managed on a server (or servers) using Ivory. These graphical objects will be interacted with by clients, and the changes made by clients will be transmitted to the server managing the object using the Ivory logging system. Throughout the semester students will add functionality to this system such as synchronization of updates by multiple clients, replication and coordination of graphical objects across multiple servers, and other distributed systems topics.
(Susan Rodger, Lenore Ramm, Eric Gramond)
JFLAP is a tool for experimenting with finite automata, pushdown automata, and Turing machines. Modifications were made to JFLAP to allow one to study proofs and incorporate more interaction with the user. Pate is a tool for studying parsing and it was modified to improve the parse trees and incorporate more interaction. Lsys, Pate, and JFLAP were written in Java, and will be used in the course CPS 140.
(Alvin Lebeck, Kelly Shaw)
CProf is a cache profiling system that helps the user/programmer locate the parts of their code which generate memory cache misses. The tool presents this information in a manner that quickly allows the user to examine the source code files, code lines, and variables that cause the greatest cache misses. Additionally, the type of cache miss (conflict, capacity, compulsory) is displayed. The user can then use this information to re-arrange her code to eliminate some cache misses.
The goal of this project is to re-write the CProf cache profiling system for use on machines running Solaris. However, the user interface is being written in Java so that only the backend of the tool will need to be rewritten for use on other platforms. This new version of CProf will be used to teach students the impact the memory system can have on the run time of their programs. Students will learn how to restructure their code to avoid costly cache misses.
Currently, students in the software development and implementation course use tools to locate which functions are performance bottlenecks. They then use this information to re-write these functions. CProf will be added to the set of tools used by students to optimize their code. It will help students pinpoint specific source lines that need to be optimized to decrease the run time resulting from memory cache misses. The use of these tools in conjunction will help the students develop skills needed to write efficient code.
Software (note: underlying executable editing system (EEL) from Wisconsin is no longer supported...so neither is CPROF.)
(Alvin Lebeck, Mithuna Thottethodi)
The tool allows the user to define and customize a processor/cache system and visualize its operations.
The GUI will allow a very simple point-and-click interface to define a processor/cache system.
Caches can be hooked to processors by "connecting" the memory references of a processor to a cache. (Connecting is done by mouse point-and-click)
Similarly defining of multi-level cache hierarchies will be possible by stacking caches and connecting the misses of one cache to be the references of the lower level cache.
Cache parameters like cachesize, blocksize, associativity, write policy, etc... can be customized through the GUI. Address partition and tag matching can be visualized.
Processor visualization will include visualization of pipelines during instruction execution.
(Jeff Vitter, David Huang)
Research is shifting from its traditional focus on the discovery of new information toward a complementary focus on the computationally intensive task of processing the information. The bottleneck in many large-scale applications is the Input/Output (or I/O) data communication between main memory and external memory (or other levels of memory). One particularly appealing mechanism of experimentation in the proposed research is our current work with TPIE---A Transparent Parallel I/O programming Environment. Conventional file systems and other commercial operating systems, do not provide the semantics necessary for implementing external-memory algorithms, especially when parallel I/O devices are used. Languages such as C, C++, and FORTRAN do not allow users to explicitly control data placement on disks. TPIE consists of an easy-to-use object-oriented interface linked to powerful disk and memory management primitives to facilitate implementation and evaluation of external-memory algorithms.
Data in several large-scale applications, such as those that arise in geographic information system (GIS), are of geometric nature, for example, involving coordinates or elevations or topographical information. Such data is easy to visualize and therefore to work with, and it ties in well with the new Center for Geometric Computing, a joint project among Brown, Duke, and Johns Hopkins Universities. The proposed project involves the design and implemention in TPIE of some large-scale algorithms and data structures useful for spatial databases and GIS. The algorithm design and TPIE implementations will provide natural synergy.
Graduate Students: Greg Keim (Fall 1997), Mike Fulkerson (Spring 1998)
Interactive algorithm animation construction. While there are a number of algorithm animation tools, current systems do not allow the instructor to interactively construct the data structures or animations, or to modify the data structures during animation. We will work on a tool that allows an instructor to design and animate simple algorthms using a point-and-click graphical user interface.
Data structures and algorithms whiteboard. We will provide a graphical environment that will allow students to easily construct and manipulate various data structures. The system will provide some facility for verifying if a construction is a legal instance of a particular data structure. For example, we might allow a student to work in the design space of arbitrary binary trees, while asking them to build a balanced binary tree. The system could have a minimal tutoring ability, if only at the level of showing the first violation.
Data structures whiteboard applet. This would allow an instructor to design interactive assignments in which the student could be asked to "update the red-black tree", or "draw the sorted binary tree after inserting this word". The student could then submit their work for later viewing or grading. This applet could be part of a larger web based homework or quiz, which could include short answer and multiple choice questions.
As part of other continuing research, the above tools will also be intergrated into a voice dialogue system (Voice and Natural Language Laboratory).
(Susan Rodger, Eric Gramond)
Modifications to JFLAP, a tool for experimenting with finite automata, pushdown automata, and Turing machines. The user can design, save a run input on a deterministic or nondeterministic machines. Materials developed used in CPS 140.
(Don Rose, Xiaobai Sun, Kee-Hyun Paik)
This research project involves numerical solutions of the differential equations
a/(2Ri) du^2/dx^2 = Cm du/dt + I_ion + I_stim dw/dt = 0.008 * u - 0.003 * w I_ion = 0.5 * (1- 0.2 * u) * (1- 0.01*u) + 0.02*u*w I_stim = [ 250 t1 < t < t2 [ 0 otherwise
where a, Ri, Cm are constants that are given, t_2-t_1 is the length of the fiber, and dt and dx are the size of time step and space descritization.
The goal is to identify numerical algorithms that are efficient, stable and, eventually, easily parallelizable to solve large scale problems.
For spatial descretization, we are using central difference with sealed boundary condition.
Among many numerical algorithms for the resulted ordinary different equations, we are currently investigating on the use of Forward Euler, Backward Euler or Trapezoid methods. The latter two methods are implicit methods. The challenges are the following.
To circumvent the problems, we are investigating the so called mixed methods. One way to mix the methods is to use Forward Euler in places where voltage change in position (du/dx) is minimal, and using one of the implicit methods to solve or resolve in areas where du/dx is large.
CURIOUS projects are designed to bring research into undergraduate courses. Current projects are being designed for the following courses.
This work is sponsored by NSF under award 9634475