Derek

This user hasn't shared any biographical information

Homepage: http://derekcarson.com


Posts by Derek

Compiler

Compiler written for Compiler Theory with Dr. Wilsey.

 

Feel free to use it as an example:

https://code.google.com/p/compilertheory/

Network Security

The final project for Network Security. Our code files for the normal client as well as our automated script to steal points/accounts from other players.

 

It is disguised as a pretty pony jpeg game so our competitors wouldn’t find the code:

https://code.google.com/p/horsepuzzle/

Large Signal Amplifier Presentation

Electronics Design Lab Project and Presentation – Dr. Peter Kossel

Project Files

We did three labs during the Electronics Design Lab course, and I had to give a presentation on one of them. Feel free to take at look at my work. I hope it is useful in some way. He definitely expects a lot out of the presentation. But if you are prepared, it is really pretty easy.

Parallel Processing GUI

Senior Design Project – University of Cincinnati

Take a parallel (or normal) program and use it as input. Let the GUI analyze the program and determine how analysis should continue. Then the GUI builds -> compiles -> executes and times -> produces graphs of these results in real time.

Project Files

The final version of this project is a Parallel Processing GUI designed to help parallel programmers characterize performance of program written in C++ using OpenMP tools. The GUI is written in Java, and the user can use it to edit, compile, and monitor the execution of his/her C++ (works whether or not the program utilizes OpenMP). Perl is used in the background to analyze the program, notifying the user of possible sections to monitor. It also modifies a copy of the code to produce differing versions to be compared. Finally, this back end compiles the copied and slightly modified version, and through a system call times the program’s execution. Because of the system calls, this program is bound to Linux/Unix.

After the program is analyzed, the user may “sweep” certain detected or pre-identified parameters to determine their affect on execution speed. This is a great way to monitor the best settings for certain algorithms that require tuning, or to see the scaling of different classes of algorithms based on size. For instance, one could observe the growth in execution of an O(n^2) algorithm vs. an O(nlogn) as n increases. This tool allows the user to see the plots of execution time, memory use, and distribution of user/system time build as each data point is collected by running the program.

The files contained are the reports from each stage of the design, and highlight the planning along the way, as well as the evolution of the concept.

VHDL USM

VHDL – Dr. Ranga Vemuri

Universal State Machine modeled in VHDL. Built in the design style of first designing a behavioral model and test benches, and then piece by piece implementing each component at the gate level.

Project Files

This is a fairly basic project, but is a good demonstration of some of the uses of VHDL. This is a hardware description of a gate level model of a universal state machine. As input, the state transition table is read into the machine, and then it makes “decisions” based on the inputs and current state. All buses in this design are scale-able, so any (memory permitting) number of states and inputs may be modeled. The gates in the library are NOT, AND, OR, XOR, and a tri-state buffer. From these gates all components are designed.

Included at the link are all the .vhd files associated with the project. The usm_gate.vhd file is the top level of the design. Also in that file are a few test benches demonstrating the use of the USM.

Low Power Experiments

Cell based low power experiments:

Measuring Leakage, Dynamic, and Crossover currents/power usage.

Interconnets experiments:

Wire tapering, wire capacitance.

Project Files

Partitioning Tool – KL Algorithm

VLSI Design Automation – Dr. Ranga Vemuri

This is a VLSI partitioning tool using the KL algorithm to solve the bipartitioning problem. It takes a netlist as input, attempts to partition it into 2 sets with a minimum cutset. The minimization is of the number of connections between the resulting netlists. The algorithm implemented is the Kernighan–Lin (KL) algorithm.

Project Files

I won’t try to do better than the Wikipedia article, but here is a basic description of the algorithm and its application to this problem:

The KL algorithm works by first dividing the graph into two sets with an equal number of vertices (presumably randomly, unless there is some prior knowledge). A cost is then calculated for each vertex. The cost is the weighted external connections (an edge connecting a vertex to the other set) minus the number of weighted internal connections (an edge connecting to a vertex in the same set). This difference is called the D value. The greater the D value, the greater the benefit of switching the vertex to the other set.

The KL algorithm simply proceeds by sorting the vertices in each set by D value, and then swapping them two at a time (one from each set). After each swap, the two that just participated in the swap are marked as no longer eligible for more swaps this pass. The D values are recalculated for all eligible vertices, and the process begins again. They are sorted, and the highest beneficial swap from each set is chosen. This continues until there are no more beneficial swaps. Then all nodes are marked eligible again, and another pass is attempted. This continues until more passes cannot improve the cost of the cut. This is the basic thinking behind the algorithm, it will actually proceed as follows:

  • Step 1: G(V,E) is graph of V vertices and E edges.
    (A,B) is initial partition of V, such that A and B are equal sized subsets with no overlap and their union covering all of V.
  • Step 2: Compute Dv = Ev – Iv for all v in V.
  • Step 3: Choose ai from A and bi from B that maximizes gi = Dai + Bai + 2caibi. The final term is the connection between the two, if it exists. Add pair (ai, bi) to queue. Remove ai and bi from allowable swaps.
  • Step 4: If there are no more eligible nodes for swap, goto Step 5.
    Else, recalculate D values for remaining eligible nodes, goto Step 3.
  • Step 5: find k to maximize the partial sum of gi from i to k in the queue. If total sum G is greater than 0, perform all swaps (a1, …, ak with b1, …, bk), and goto Step 2. Else, end.

This is a deterministic heuristic.

This was one of my first projects writing software from scratch, and it can definitely be seen from my design. I was pretty new as far as my C++ skill, so there is a lot of room for improvement in the design (as far as object orientation). However, it does perform correctly. I learned a lot from this project, and I think improvement can be seen from this project to the next I did, the Placement/Routing tool.

Placement/Routing Tool

VLSI Design Automation Placement/Routing Tool

All cells are the same size, and contain 4 terminals (blackbox representation).

Given a netlist, minimize the area necessary for placement.

Netlist -> Initial Placement -> Simulated Annealing with Route Approximation -> Routing -> Design

Project Files

JTAG BSD Design

Boundary Scan Design

Completed RTL Design -> Scan Chain Addition -> JTAG Boundary Scan Addition

ATPG -> Test Coverage

Project Files