Mini-project: Basic Systolic Algorithms

Here are two very basic simulation applications for two systolic algorithms (aka. Instruction Systolic Arrays). Their main purpose is to illustrate how such systolic algorithms work on a given data set. Both simulators have been designed for the Systolic Algorithms course I've attended at my university.


Application no.1: Systolic Array Sorting 

The first algorithm I have implemented aims to solve the simple problem of Systolic Array Sorting. The idea of the problem is the following: given an uni-dimensional systolic system large enough to store the entire contents of an arbitrary array, devise a method of sorting the array in linear time (i.e. algorithm complexity of O(n)).

The systolic system that solves this problem is extremely simple:

1.Each systolic cell can store at most two values (a base value and an auxiliary transport value).

2.Each cell communicates with its left and right neighbors (it can receive a value from the left neighbor and can pass a value to its right neighbor = data flow model). When a cell receives a value from the left it stores it as a transport value.

3.At each step (system tact) each systolic cell (that holds both a base and a transport value) takes a simple decision: it passes to its left neighbor the lowest value between the base value and the transport value and stores the highest of the two.If the cell holds only a base value then it does not take any action.

The systolic system is initialized by loading the initial unsorted array (each array element is loaded as the base value of a cell cell). The output of the system (i.e. the right-most cell) should be connected to a data structure where we wish to store the sorted array. 
At each step we simply input into the systolic system a predefined maximal value (i.e. a value greater than any value in the unsorted array) by "communicating" it to the left-most cell of the systolic system.
The entire key (and idea behind any systolic algorithm) is that the "communication" process is parallel.  
If we have an array of size n the sorting process will take exactly 2*n steps which translates into a complexity of O(n).

Application no.2: Systolic Matrix Multiplication

The second application simulates systolic matrix multiplication. The systolic architecture needed to solve this problem is a bit more complicated than the one used in the first example. The cells are organized as a matrix (the size of which is equal to the one of the expected result matrix). Each cell can communicate with its 4 neighbors (receives values from the cells to the left and above and sends them to the cells to the right and below). Also, the individual organization of each cell is more complicated, as each cell can hold 3 values and execute 2 operations (addition and multiplication).
For a detailed explanation of the systolic matrix multiplication algorithm please see this page.
The complexity of this systolic algorithm is O(n) as it would take 3*n steps to multiply two matrices of size nxn. In order to simplify the observation of the process, in the simulation application, each step is further divided into 3 sub-operations.

Although fairly simple, these two examples can easily show the power of systolic architectures as they offer linear solutions to problems which normally have a higher complexity (O(n*log(n)) for sorting and O(n^2.376) for matrix multiplication)). 

You can download these two simulators by clicking here or from the Downloads box (SystolicSimulators.zip).  

Application platform: WinNT

Mini-project: DCrypt

DCrypt is a small program I wrote for my network security class. It features 2 encryption ciphers and the DES algorithm. It was written in Delphi and allows for text to hexadecimal encryption and hexadecimal to text decryption.

The first cipher I included in DCrypt is the Viginere cipher. You can find out detailed information about this encryption method here. In this implementation, the cipher can process full ASCII text but only encodes the letters (A-Z). It also converts small letters to capital letters.
The second cipher I implemented is the Bifid cipher. In the current implementation this cipher can only process text containing: A-Z letters and a few special characters . It too converts small letters to capital leters.
Finally, the DES implementation encodes full ASCII text using 64 bit blocks and a 64 bit key and does not perform any conversions on the text. The code for this part of the application is largely based on a Delphi unit written by Francoise PIETTE.
You cand download a fully working version of the application (source code included) by clicking here or from the Downloads box (DCrypt.zip). Here are two screenshots:

Application platform: WinNT

Meet Wordle

For someone who's main field of interest is IT , I must shamefully admit that there are still very cool programs out there that, though eluded my attention :)), are well known by almost all of my friends. One such program is Wordle created by Jonathan Feinberg. Wordle is basically a toy for generating "word clouds" from given input text. In these clouds, greater prominence is given to the words that appear more frequently in the input text. What makes it unique is the fact that you can tweak your clouds with different fonts, layouts, and color schemes and save them as images for the whole wide word to see.

Wordle also has an option for genereting clouds from RSS feeds.
Here is are two clouds obtained for two of my posts. Can you guess for which ones? :))

(click image to enlarge)

(click image to enlarge)

Mini-Project: Shutdown Timer

Lately I got used to falling asleep while watching TV on my laptop and as my TV-tuner software is quite primitive and doesn't have the option to shutdown the computer after a predefined period of time, I started to search the web for a simple shutdown timer application. I didn't want a fancy application with a lot of options just a basic program that will enable me to select a period of time after which the system would shutdown and that, if needed, could cancel the shutdown command.
As the first two applications found by Google that met my over demanding request were not free I decided to write my own program. I remembered a nice and useful piece of code I once stumbled upon on Torry's Delphi Pages that enables a process to aquire privileges on WinNT platforms. I used it to aquire the 'SeShutdownPrivilege' and after that, the rest of the program was done in no more than 15 minutes.
You cand download a fully working version of Shutdown Timer (source code included) by clicking here or from the Downloads box (ShutdownTimer.zip). Ohh ... and here is a screenshot of my latest mezmerizing achivement in the field of computer software:

Application platform: WinNT

Project: Bandwidth reduction

This post is a follow-up to the problem of bandwidth reduction presented earlier. I've done a small Delphi application that can generate sparse matrices of various sizes and densities (the density of a sparse matrix is the percent of non-zero elements is contains) and that features 3 (actually more like 2 :)) ) bandwidth reduction algorithms. The first algorithm is the original Cuthill-McKee algorithm, the second one is the Reverse Cuthill-Mckee algorithm (both of which have been covered in detail) and the third algorithm I've decided to implement is a genetic algorithm.

I must say that I was very curious to see how a genetic algorithm would perform on this problem as the bandwidth reduction problem is basically a combinatorial problem. As it turns out there is a really nice study performed by A. Lim, B. Rodrigues and F. Xiao that covers this exact topic. The three researchers carry on the work of R. Marti and V. Campos in trying to use a metaheurisc approach in order to obtain better results than the classic bandwidth reduction algorithms (RCM and GPS).

Although genetic algorithms perform very well in global search they are less suitable for tuned search. and as such, Lim, Rodrigues and Xiao combined the genetic algorithm with a hill climbing algorithm. The resulting hybrid algorithm performs very well and generally produces solutions of better quality than the Reverse Cuthill-McKee algorithm.
My implementations of the CutHill-McKee algorithm and of the genetic algorithm are by no means optimal (the genetic algorithm is also slightly modified). As such, both algorithms perform relatively poor (in terms of speed) compared with their creators' estimations. The main purpose of this project however, was to show that in the field of NP-complete problem solving, metaheuristic approaches, although considered rather slow, can be expected to produce results of very good quality.
You cand download a fully working version of the application (source code included) by clicking here or from the Downloads box (BandwidthReduction.zip). Here are two screenshots:

And here is an example of how RCM and the hybrid metaheuristics' based algorithms performed on a 150x150 randomly generated simetric sparse matrix with a density of 3.5% (788 non-zero elements):

1. The initial sprase matrix. (bandwidth = 142)

2. The solution obtained using RCM. (bandwidth = 81)

3. The solution obtaind using the hybrid genetic + hill climbing algorithm. (bandwidth = 65). This solution was obtained after 15 generations using a mutation rate of 40%.

Application platform: Win32