Title page for ETD etd-1629131549741341

Type of Document

Master's Thesis

Author

Kahne, Brian C.

URN

etd-1629131549741341

Title

A Genetic Algorithm-Based Place-and-Route Compiler For A Run-time Reconfigurable Computing System

Degree

Master of Science

Department

Electrical and Computer Engineering

Advisory Committee

Advisor Name	Title
Peter M. Athanas	Committee Chair
Charles E. Nunnally	none
James R. Armstrong	none

Keywords

genetic algorithm
configurable computing wormhole
run-time reconfiguration
routing
placement

Date of Defense

1997-05-14

Availability

unrestricted

Abstract

Configurable Computing is a

technology which attempts to

increase computational power by

customizing the computational

platform to the specific problem at

hand. An experimental computing

model known as wormhole run-time

reconfiguration allows for partial

reconfiguration and is highly scalable.

In this approach, configuration

information and data are grouped

together in a computing unit called a

stream, which can tunnel through the

chip creating a series of

interconnected pipelines.

The Colt/Stallion project at Virginia

Tech implements this computing

model into integrated circuits. In

order to create applications for this

platform, a compiler is needed which

can convert a human readable

description of an algorithm into the

sequences of configuration

information understood by the chip

itself. This thesis covers two

compilers which perform this task.

The first compiler, Tier1, requires a

programmer to explicitly describe

placement and routing inside of the

chip. This could be considered

equivalent to an assembler for a

traditional microprocessor. The

second compiler, Tier2, allows the

user to express a problem as a

dataflow graph. Actual placing and

routing of this graph onto the

physical hardware is taken care of

through the use of a genetic

algorithm.

A description of the two languages is

presented, followed by example

applications. In addition,

experimental results are included

which examine the behavior of the

genetic algorithm and how alterations

to various genetic operator

probabilities affects performance.

Files

Filename		Size	Approximate Download Time (Hours:Minutes:Seconds)
Filename		Size	28.8 Modem	56K Modem	ISDN (64 Kb)	ISDN (128 Kb)	Higher-speed Access
	etd.pdf	325.59 Kb	00:01:30	00:00:46	00:00:40	00:00:20	00:00:01