Gur Saran Adhar
January 9, 1992

Thru this note I am requesting release time equivalent to three credit hours teaching time during the Fall 92 semester. I plan to use this time for two activities: (a). complete research on new parallel algorithm for graph unfolding, and (b). prepare a grant proposal to be submitted to National Science Foundation for funding to incorporate Hardware Description Language in Computer Architecture course csc442.

Parallel Algorithms for graph unfolding:

The graph unfolding problem can be stated as:

Given a graph G = (V,E) defined by its vertex set V and edge set E what is an optimum representation of embedding of G on a plane, where a representation is said to be optimum if it corresponds to fewest edge crossings.

Unfolding problem arises in VLSI design where devices correspond to vertices of graph and wires correspond to edges in the graph. Wire crossings are undesirable and should be minimized at all cost since a wire is forced to change layers two time in order to implement an edge crossing. The problem is known to be NP-complete and therefore attempt is made to find approximate algorithms with provably known bounds on their solution.

I have obtained initial results on graph unfolding problem however much theoretical characterization of results remains to be done. I would like to complete the research and write the results for publication during Fall 92 semester.

VHDL in Computer Architecture:

I wish to make a grant proposal to National Science Foundation for incorporating the use of VHDL in computer architecture course csc442.

VHDL ( VHSIC Hardware Description Language) is a high level language for describing digital electronic systems. It arose out of the United states Government's Very High Speed Integerated Circuits (VHSIC) program. VHDL is used for both describing the function and structure of a design as well as it is used to simulate the design before being manufactured. It offers exciting possibilities for a student in computer architecture to try out different architectures and evaluate performance of alternative designs. In addition it provides valuable insight in the design process. For this reason it has been used by students of Computer Architecture course to describe and validate their designs at many universities all over the country.

I would like to incorporate the use of VHDL in Computer architecture course csc442. For this purpose I would make a grant proposal to NSF during Fall 92 for the purchase of VHDL compiler to be run on the Sequent Balance machine.