Dan Gibson

Other Projects

CS/RADAR

CS/RADAR is a location discovery and tracking system, based on the RADAR project done at Microsoft Research. CS/RADAR uses local RF (802.11) conditions and RF-Maps to determine the location of an 802.11-equipped device. It uses a client/server model to separate RF sampling from location discovery, thereby reducing computational and storage requirements on a given device.

Abstract:

Recent work done at Microsoft and elsewhere suggests that the concept of RF-based location and tracking (RADAR) is useful from the perspective of user location and tracking in local-area networks. RADAR operates by sampling signal strengths from some number of nearby transmitters. These samples are compared against samples of known locations, stored in an RF-based map.

We have replicated a portion of the Microsoft RADAR system, and speculate on possible adaptations of the RADAR concept for use in ubiquitous computing scenarios and wireless sensor networks. We have extended the RADAR concept to include a client/server model, which significantly reduces storage and processing requirements of the mobile device.

CS/RADAR was developed with Jake Adriaens for Prof. Seapahn Megerian's ECE 902 class in Fall, 2004.

Paper

Binaries:

Win32

Source (C/C++, MFC):

Win32

RF-Maps of Engineering Hall

Note: To run the binaries, the program "HP Client Manager" must be running on your machine.

Distributed Shared Memory over IP Networks

Chuck Tsen and I developed this implementation of distributed shared memory over networks of workstations as our final project for Mark Hill's CS 757 class in Spring 2005.

Abstract:

Parallel programming is becoming an increasingly popular method of improving computer performance. Unfortunately, parallelized hardware remains expensive in the form of complicated symmetric multiprocessors and high-end server platforms. To provide a more available platform for parallel execution, we revisit the topic of implementing distributed shared memory on networks of commodity workstations. We discuss the implementation and evaluation of a distributed shared memory system, using existing Ethernet/IP-based networks for communication between logical threads. Our implementation leverages user-space programming primitives to provide a software-only solution for executing parallel programs on commodity hardware and operating systems. We demonstrate application-dependent speedup over uniprocessor executions for simulated workloads, even on small networks. We also observe the effect of heterogeneity in our network, and its significant performance impact.

Paper

PowerPoint

Binaries:

Not available

Source (C++):

Linux

A Software Layer for Disk Fault Injection

Jake Adriaens and I worked on this project for Remzi Arpaci-Dusseau's CS 736 class in Spring 2005 as our final project.

Abstract:

Increasing demands for reliability, fault isolation, and fault tolerance have emphasized the need to study systems under failure conditions. Commodity disk systems have been studied for many years with simple assumptions about how they fail. To provide enabling technology for new research in more reliable file systems, disk system, and I/O interfaces, we present a flexible, software-based fault injection system, targeted for commodity disks running in conjunction with a commodity operating system. We present five sophisticated but general failure models, and a simple interface to allow arbitrary faults to be injected rapidly and without permanent hardware damage. We also evaluate the performance of a common file system utility to detect these faults, and present a summary of our findings.

Paper

PowerPoint

Binaries:

Not available

Source (C):

Linux

Multithreaded Matrix Multipliers

This program suite is the result of an assignment for CS/ECE 757 in Spring, 2005.  The programs find the product of three matrices.  The programs use two parallel programming models: shared memory and message passing.  The message passing is implemented using MPI, the shared memory using the POSIX libraries.  I developed these programs on cabernet.cs.wisc.edu, a 16-processor Sun E6000.  I cannot guarantee these programs will work without modification outside of that environment.  In general, each program takes some number of arguments, and computes its answer in file "matrix".  To run the MPI program, you must use the binary mpirun.ch_shmem, part of the MPI package.

These multipliers are meant mostly as a demonstration of parallel programming, not a demonstration of how to write fast matrix multipliers.  The fastest matrix multiplication algorithms consider many factors that I have ignored--cache block size, matrix equalities, and other tricks that would obfuscate the parallelism obvious to this problem.

Write-up

Binaries:

Not available

Source (C):

Linux - randmatrix and unimatrix

Linux - sharedmatrix

Linux - passingmatrix

Measurement of the EXT2 File System

This project was assigned as part of the coursework for CS 736 (Prof. Remzi Arpacci-Dusseau).  It uses the built-in cycle counters of the x86 platform to measure a few parameters of the EXT2 file system.

Write-up

Binaries:

Not available

Source (C/C++):

Not available

Implementation of Kernighan-Lin Bi-Partition Heuristic

The Kernighan-Lin heuristic parititions a circuit while attempting to minimize the number of nets that cross the partition.  This implementation was developed for Prof. Yu Hen Hu's ECE 556 class in Fall, 2004.

Paper

Binaries:

Win32 (DOS)                Linux

Source (C/C++):

Win32 (DOS)                Linux

Input Files:

Win32 (DOS)                Linux

Circuit Floorplanner using Simulated Annealing

This floorplanning tool uses a random-search algorithm, bounded by Simulated Annealing, to find a low-area floorplan for a given circuit.  This implementation was developed for Prof. Yu Hen Hu's ECE 556 class in Fall, 2004.

Paper

Binaries:

Win32 (DOS)                Linux

Source (C/C++):

Win32 (DOS)                Linux

Input Files:

Win32 (DOS)                Linux

Implementation of TimberWolf Standard-Cell Placement Tool

This is a simplified implementation of the popular TimberWolf Standard-Cell Placement Tool, developed for Prof. Yu Hen Hu's ECE 556 class in Fall, 2004.

Paper

Binaries:

Win32 (DOS)

Source (C/C++):

Linux

Input Files:

Win32 (DOS)                Linux

Genetic Placmement with Meta-Genetic Parameter Optimization

This placement tool was based on the work done in:

K. Shahookar and P. Mazumder.  A genetic approach to standard cell placement using meta-genetic parameter optimization.  IEEE Transactions on Computer Aided Design, 9(5):500-511, May 1990.

The implementation follows the description found in the paper above as exactly as possible.  The paper describes the tool and compares its performance to the implementation of TimberWolf, above.

This implementation was developed for Prof. Yu Hen Hu's ECE 556 class in Fall, 2004.

Paper

Binaries:

Win32 (DOS)

Source (C/C++):

Win32 (DOS)                Linux

Input Files:

Win32 (DOS)                Linux

Phalanx: Combination Branch Prediction in SimpleScalar

This project surveyed possible combinations of popular branch predictors using SimpleScalar 3.0.

Abstract:

Branch prediction is of great importance to deep-pipeline design. Speculative execution is necessary to more fully utilize chip resources, and the need for issuing correct speculative instructions leads to demand for very accurate predictors. Single predictors have been successful in predicting branches with high accuracy for many workloads, though the increasing number of instructions in-flight demands increasingly more accurate predictors. Hybrid predictors show promise of fulfilling this demand, combining the capabilities of many individual predictors at the cost of increased predictor size.

Phalanx is an implementation of a quickly reconfigurable hybrid predictor, intended to evaluate the effectiveness of many different predictor combinations. We have surveyed the effectiveness of several combinations of popular predictors against the SPEC2000 integer benchmark suite. The total size of memory size allocated to branch prediction is fixed at 8 KB. Phalanx divides this space among sub-predictors. Each configuration has been compared against its constituent predictors--each of which has been allocated memory equal to the combined size of all predictors in Phalanx.

This project was implemented for Prof. Mark Hill's CS/ECE 752 class in Fall, 2004, by myself, Chuck Tsen, and Inge Yuwono.

Paper

Binaries:

Not Available

Source (C):

Not Available

sim

sim was part of the semester project prepared by myself, Jake Adriaens, John Schmoller, and Igne Yuwono for ECE 554 in Spring 2003.  In that project, a simple five-stage pipelined processor was implemented in Verilog HDL, as well as a number of test and demonstration programs.  Modeled after the isim MIPS/RISC simulator, sim is the instruction-level simulator used to develop programs for our target ISA.  

Reference:

sim Reference Manual

Binaries:

Win32 (DOS)

Source (C/C++, ASM):

Win32 (DOS)

Assembly programs

ECE 554 Semester Project

ECE 554 requires students to implement a pipelined processor in Verilog HDL, which is then prototyped using Xilinx FPGAs.  I worked on this project with Jake Adriaens, John Schmoller, and Igne Yuwono.

Paper

Triominos

The triomino problem is this:

Given an NxN grid (N=2^k) with one "missing" location, completely fill the remaining grid area with L-shaped "triominos."

This project evolved from an assignment in CS 577: Introduction to Algorithms.

Binaries:

Win32

Source (C/C++,MFC):

Win32

Multi-Process String Matcher

Another CS 577 project, this program suite compares the performance of three popular string matching algorithms: Boyer-Moore, Horspool, and Brute Force.  Each matcher is spawned as a separate process, and a master process presents a graphical result of the number of comparisons.

Binaries:

Win32

Source (C/C++,MFC):

Win32

Inputs:

Win32

Genetic Algorithm Demonstration

This small program demonstrates how the genetic algorithms operate in general.  This algorithm begins with a population of random 32-bit numbers and attempts to "breed" the value -1 from these numbers (note that -1 = 0xFFFFFFFF, or all 1's in binary, on 32-bit machines).  This program illustrates a genetic process by which the most fit members of the population are chosen for breeding of new population members, and demonstrates the role of mutation in the genetic search process.

The code was developed using the Borland Turbo Compiler (bcc32.exe) and Microsoft's Visual C compiler (cl.exe).

Binaries:

Win32 (DOS)

Source (C/C++):

Win32 (DOS)   Linux

ANSI Color Demonstration

The ANSI Color Codes are as hard to remember as ASCII codes, but aren't documented nearly as well.  This small program demonstrates the ANSI Color Codes, then exits.  No need to remember if "\033[31m" means "green" or "red".

Binaries:

Not Available

Source (C/C++):

Linux

Linux "Libraries"

A small collection of useful code snippets:

fatals.h and fatals.cpp:  Some rudimentary "quit-with-error-message" functions, that have printf-like argument passing.  I haven't bothered to investigate how to handle functions with an arbitrary number of functions, but I have approximated arbitrary argument types by using many redundant function prototypes and definitions.

argsparse.h and argsparse.cpp: I wrote these in response to the lengthy argument processing code I wrote for the VLSI EDA projects in the Graduate Projects section.  I have yet to use them, but they might be useful for programs that expect a lot of arguments.

hrtime.h: A very simple inline functiont that calls the cycle-accurate x86 counters, using a block of ASM code. Philippe Gerum actually wrote the code, but I find it to be very useful.  I did a few simple disk measurement experiments using this function.  (Original source: https://mail.rtai.org/pipermail/rtai/2003-November/005660.html)

rand32.h and rand32.cpp: The random number generator in C/C++ only generates 15-bit random values, on the range [0,0x7FFF].  Some functions in these files extend the functionality of rand() to 32 bits, and provide some typical rand()-like functions, like randOnRange(int low, int high)

textcolors.h: This header includes macros for most of the useful ANSI color codes.

progbar.h and progbar.cpp: This Linux-only progress bar is object-oriented and very easy to use and modify.

Binaries:

Not Available

Source (C/C++):

Linux

Blackjack

Boredom is the mother of all programs, especially DOS-based card games.  I enjoyed writing and playing this Vegas-style single-deck Blackjack game on a long trip to the west coast.

Binaries:

Win32 (DOS)

Source (C/C++):

Win32 (DOS)

EggTimer3

EggTimer3 is a simple minute/second counter that I made because I found myself too absorbed to glance at a clock.  EggTimer3 will emit a siren-like tone after a user-entered time has elapsed.  Simple, but useful.

Binaries:

Win32

Source (C/C++,MFC):

Win32

Sorting Algorithm Implementations

Below are implementations of common sorting algorithms in C/C++.  Feel free to use these algorithms for your own projects.

Binaries:

N/A

Source (C/C++):

BubbleSort                InsertionSort                QuickSort                MergeSort                All

HoursCalculator

HoursCalculator is one of four programs I have developed under contract from Princeton House Private Residence Hall.  This tool is used to determine payroll information for hourly employees.  The binaries and source for this program are proprietary, and are not available.

Binaries:

Not Available

Source (C/C++,MFC):

Not Available

Building Manager

This program is one of four programs developed under contract from Princeton House Private Residence Hall.  This tool was not deployed, but is fully-functional and is could be used to keep detailed information on various rooms and common areas.  It uses a point-and-click interface which allows nearly all program dialogs to be accessible in a single click.

The binaries and source for this program are proprietary, and are not available.

Binaries:

Not Available

Source (C/C++,MFC):

Not Available

LabelMaker

LabelMaker is a parsing and re-ordering tool developed under contract from Princeton House Private Residence Hall.  It is an advertising tool that parses student data purchached from DOIT into useable formats for mass-mailing and mass-emailing.

The binaries and source for this program are proprietary, and are not available.

Binaries:

Not Available

Source (C/C++,MFC):

Not Available

Resource Manager

Resource Manager is an inventory management tool developed under contract from Princeton House Private Residence Hall.  Resource Manager 1.0 was deployed in August of 2002, and Resource Manager 2.0 was deployed in January, 2005.  It is used primarily to track the location of items on loan to students, and provides user-level accounting, printable reports, quick searching, and SHA hashing to protect data.

The binaries and source for this program are proprietary, and are not available.

Resource Manager 1.0

Resource Manager 2.0

Binaries:

Not Available

Source (C/C++,MFC):

Not Available

Best viewed on Google Chrome. Get it here.