Date: Nov. 22, 1995

Rank: Associate Professor

Department: Mathematical Sciences

Terminal Degree: Ph.D.

Received: July 1990

Year of Initial Appointment at UNCW: 1989

Proposed Period of Reassignment:

Beginning Date August 1996
Ending Date June 1997

Is Other Funding being Sought ? Yes

If yes please state sources

Distributed Parallel Processing Laboratory,
Department of Computer Science,
University of Aizu, Aizu-Wakamatsu, Fikushima Pref. 965-80, JAPAN

Abstract (maximum of 175 words):

Very Large Scale Integration or VLSI plays a major role in the development of electronic systems. VLSI Physical Design Automation is the study of algorithms and data structures related to the physical design process of the micro-electronic chips used in electronic systems. The objective of VLSI design automation is to study optimal arrangements of devices on a plane and efficient interconnection schemes between these devices to obtain the desired functionality. Tolerance in VLSI design refers to flexibilty in regard to the interconnections between the devices. In this research we will examine the effects of introducing tolerance into many design problems and discover efficient new algorithms to solve such problems.

1  Research Theme: Algorithms for VLSI Design-With-Tolerance

Very Large Scale Integration or VLSI plays a major role in the development of electronic systems. VLSI Physical Design Automation is the study of algorithms and data structures related to the physical design process of the micro-electronic chips used in electronic systems. The objective of VLSI design automation is to study optimal arrangements of devices on a plane (or in a three dimensional space) and efficient interconnection schemes between these devices to obtain the desired functionality. Since space on a silicon wafer, the most common medium for fabricating micro-electronic chips, is very expensive real estate, the algorithms must use the space very efficiently to keep down the costs and to improve the yield. The arrangement of devices also plays a important role in determining the performance of a micro-electronic chip. Finally, algorithms must be efficient and should be able to handle very large designs.

Since many of the objects in VLSI physical design are very simple geometric shapes such as rectangles and lines, physical design algorithms can be described using the tools of graph theory, the study of relationships between objects. In this respect physical designs automation can be modeled as the study of graph algorithms for the manipulation of geometric objects in two and three dimensional space.

2  Proposed Project and Expected Results

Most VLSI physical design is accomplished in two steps. First the devices are placed (in the placement phase), and thereafter interconnections are made between devices (in the routing phase). Tolerance in VLSI design refers to flexibilty in regard to the interconnections between the devices. Tolerance is high during the placement phase and reduces once the placement is complete. In fact most algorithms for routing do not provide any flexibility at all. In this research we will examine the effect of introducing tolerance into many design problems and discover efficient new algorithms to solve them.

At present, algorithms for the channel routing problem in VLSI use interval graphs - a type of graph that shows the overlapping relation between wires in a channel [], []. These interval graphs become inadequate as a model when the interconnections are not point-to-point but instead allow some tolerance at the terminals of the nets.

One graph representation which exhibits the overlapping relation of intervals-with-tolerance is the class of tolerance graphs [], [], [], [], []. Tolerance graphs are much more general and provide richer models to incorporate reallife facts about interconnections.

Although some graph-theoretic properties of tolerance graphs have been studied [], tolerance graphs have not yet been used to model physical VLSI design problems. The first goal of the proposed research will be to examine the possibility of using tolerance graphs as a model for the relation among the wires in a channel instead of the usual interval graph. The two-dimensional representation of tolerance graphs [] lends itself to mapping into efficient data structures and presents itself as an excellent candidate for algorithmic research to solve VLSI design problems that arise inside a channel.

The second goal of the research is inspired by the following mathematical observation.

Tolerance graphs, whose complement corresponds to two-dimensional partial orders, represent the overlapping relation among one dimensional intervals-with-tolerance.

This mathematical fact suggests the distinct possibility that

three dimensional partial orders can be successfully defined to represent the overlapping relation among two-dimensional geometric shapes with tolerance, such as rectangles.

If it is indeed possible to define such graph object, say higher dimension tolerance graphs, we could begin to address more important question: is there a mapping of rectangles-with tolerance into three-dimensional rectilinear space which models the overlapping relation of rectangles of a VLSI design when the rectangles are allowed to be moved in either direction within the chip area to some extent?

A positive answer to this question will allow a large number of VLSI design problems to be solved on a much more realistic graph model whenever the overlapping relation between two-dimensional rectangluar shapes is of importance [], [].

3  Benefits to Faculty Memeber, Department, and University

The proposed research activity will deepen the research involvement and enhance faculy member's knowledge in a very important area of computer science.

The proposer will give several departmental seminars to present the results of the research work to other faculty members at the conclusion of reassignment. Separate lectures will be planned for students and for general audience. Results of the research will be published in a refereed journal.

The reassignment will provide opportunity for the faculty member to interact with graduate faculty at the University of Aizu and gain valuable experience in developing a graduate program in Computer Science here at UNCW.

The proposer has jointly authored several research papers with Dr. S. Peng of the University of Aizu. A proposal for salary support during the year has been submitted to the University of Aizu.

References

[]

Giri Narasimhan, and Rachael Manber Stability Number and Chromatic Number of Tolerance Graphs, Univ. of Wisconsin Madison Computer Science Department Tech Report, 1988.

[]

Martin Charles Golumbic, Clyde L. Monma, and William T. Trotter, Tolerance Graphs, Discrete Applied Mathematics, 1984, 157-170.

[]

Dieter Kratsch, and Lorna Stewart, Domination on Cocomparability Graphs, Southeastern Conf. on Combinatorics, Graph Theory, and Computing, (1989).

[]

Stefen Felsner, Tolerance Graphs and Orders, Tech. Report No. 309/1991, Technische Universitat Berlin, Germany.

[]

Bogart, K.P., Isaak, G., Langley, L. and Fishburn, P.C., Proper and Unit Tolerance Graphs, Tech. Report No. 91-74/1991, DIMACS.

[]

Langley, Larry L., The Predecessor Successor Relation and a recognition algorithm for orders of dimension two, Tech. Report No. PMA-TR92-102, Department of Mathematics and Computer Science, Dartmouth College.

[]

Bogart, Kenneth P., and Trenk, Ann N., Bipartite Tolerance Orders,

[]

Kuh, Ernest S., and Kashiwabara, T., and Fujisawa, T., On Optimum Single Row Routing, IEEE Trans. Circuits Syst., vol. CAS-26, pp.361-368, June 1979.

[]

Yoshimura, T., and Kuh, E.S., Efficient Algorithms for Channel Routing, IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, VOL. CAD-1, No.1, Jan. 1982.

[]

Savage, J.E., and Wloka, M.G., Parallel Constraint Graph Generation, Advances in VLSI 1989.

[]

Willaim Wei-Lian Lin, Placement Problems arising from Automatic Logic Compilation, CS-TR-201-89, Ph.D. Thesis, Department of Computer Science, Priceton University 1989.

From s-peng@u-aizu.ac.jp Thu Nov  9 02:55 EST 1995
Received: from u-aizugw5.u-aizu.ac.jp by cms.uncwil.edu with SMTP id AA29291
  (5.67a/IDA-1.5.cgs.2.13.95 for <adhar@cms.uncwil.edu>); Thu, 9 Nov 1995 02:54:59 -0500
Received: from pross62.u-aizu.ac.jp (pross62 [163.143.161.103]) by u-aizugw5.u-aizu.ac.jp (8.6.10+2.4W/3.2W-u-aizugw.u-aizu.ac.jp03/30/94) with ESMTP
    id QAA06193 for <adhar@cms.uncwil.edu>; Thu, 9 Nov 1995 16:54:33 +0900
Received: from localhost (localhost [127.0.0.1]) by pross62.u-aizu.ac.jp (8.6.10+2.4W/3.2W-rsvss2.u-aizu.ac.jp03/17/94) with ESMTP
    id QAA23721; Thu, 9 Nov 1995 16:54:32 +0900
Return-Path: <s-peng@u-aizu.ac.jp>
Message-Id: <199511090754.QAA23721@pross62.u-aizu.ac.jp>
To: "G. Adhar" <adhar@cms.uncwil.edu>
Cc: s-peng@u-aizu.ac.jp, s-peng@u-aizu.ac.jp
Subject: Re: Here is .ps file of the proposal..
In-Reply-To: Your message of "Thu, 09 Nov 1995 02:00:25 EST."
             <199511090700.AA28373@cms.uncwil.edu>
Date: Thu, 09 Nov 1995 16:54:31 +0900
From: Shietung Peng <s-peng@u-aizu.ac.jp>
Content-Type: text
Content-Length: 556
Status: RO

Hi, Dear Adhar,

I got your file.
We should submit the application form tomorrow (11/10).
What I need from you is your resume.
Please send it by e-mail to me today.
The research plan looks fine.
Please give it a proper title (Research Theme :.......)
Then, put the file you just completed under "Content of Research".
Also specify the duration of research (e.g., half year 96/6/1 - 96/11/30).
I need all the information today.
I will start to fill up the documnet of my part.
Hope everything will be okay.

Shietung Peng

From s-peng@u-aizu.ac.jp Thu Nov  9 21:26 EST 1995
Received: from u-aizugw5.u-aizu.ac.jp by cms.uncwil.edu with SMTP id AA09361
  (5.67a/IDA-1.5.cgs.2.13.95 for <adhar@cms.uncwil.edu>); Thu, 9 Nov 1995 21:26:10 -0500
Received: from pross62.u-aizu.ac.jp (pross62 [163.143.161.103]) by u-aizugw5.u-aizu.ac.jp (8.6.10+2.4W/3.2W-u-aizugw.u-aizu.ac.jp03/30/94) with ESMTP
    id LAA14163 for <adhar@cms.uncwil.edu>; Fri, 10 Nov 1995 11:26:04 +0900
Received: from localhost (localhost [127.0.0.1]) by pross62.u-aizu.ac.jp (8.6.10+2.4W/3.2W-rsvss2.u-aizu.ac.jp03/17/94) with ESMTP
    id LAA29222; Fri, 10 Nov 1995 11:26:04 +0900
Return-Path: <s-peng@u-aizu.ac.jp>
Message-Id: <199511100226.LAA29222@pross62.u-aizu.ac.jp>
To: "G. Adhar" <adhar@cms.uncwil.edu>
Cc: s-peng@u-aizu.ac.jp, s-peng@u-aizu.ac.jp
Subject: Re: This one is bit better..
In-Reply-To: Your message of "Thu, 09 Nov 1995 13:45:03 EST."
             <199511091845.AA03908@cms.uncwil.edu>
Date: Fri, 10 Nov 1995 11:26:03 +0900
From: Shietung Peng <s-peng@u-aizu.ac.jp>
Content-Type: text
Content-Length: 328
Status: RO

Dear Prof. Adhar,

I got all your emails.
This morning I filled out the application form as well as
necessary documents and sent them to dept. chair.
We should know the result early next year.
I hope you can come here. It is a very beautiful place
(a lot of snow during winter, wonderful for skii).

sincerely,

Shietung Peng

I. Education

Institution	Field of Concentration	Years	Degree
University of Maryland	Computer Science	1986-1989	Ph.D
Baltimore County
University of Maryland	Computer Science	1984-1986	M.S.
Baltimore County
Indian Institute of Management	Business Management	1975-1987	M.B.A.
Bangalore, India
Agra University, India	Electrical Engineering	1970-1974	B. Sc. Eng.

II. Professional History

Position/Rank	Institution	Dates
Research Assistant	University of Maryland	Jan. 86 to May 88
Graduate teaching assistant	University of Maryland	Aug. 84 to May 89
Engineer	Engineers India Limited	Aug. 82 to Aug. 84
Assistant Engineer	Engineers India Limited	Aug. 79 to Aug. 82
Junior Engineer	Engineers India Limited	Aug. 78 to Aug. 79
Trainee Engineer	Engineers India Limited	Aug. 77 to Aug. 78
Lecturer Electrical Engineering	Agra University, India	Aug. 74 to May 75

III. Publications in Refereed Journals:

0.

``Parallel Algorithms for k-tree recognition and its applications'',
HICSS-27, 27th Hawaii International Conference on System Sciences, 1994. jointly with Shietung Peng.

``Mixed Domination in trees- A Parallel Algorithm'',
Congressus Numerantium, vol. 100-104, 1994, jointly with Shietung Peng.

``Parallel Algorithms for Finding Connected, Independent, and Total Domination in Interval Graphs'', Parallel Algorithms and VLSI Architectures, June 1991, Elsevier Publications, jointly with Shietung Peng.

``Parallel Algorithms for Cographs and Parity Graphs with Applications'', Journal of Algorithms, Vol. 11, 1990, pp 252-284, jointly with Shietung Peng.

``Parallel Algorithm for Maximum Matching in Cographs,''
Congressus Numerantium, Vol.77, December 1990, pp 217-227, jointly with Shietung Peng.

``Parallel Algorithm for Cographs: Recognition and Applications'',
Springer Verlag Series- Lecture Notes in Computer Science, 1989, jointly with Shietung Peng.

``Parallel Algorithms for Complement Reducible Graphs and Parity Graphs'', Proceedings of the International Conference on Computing and Information, May 1989, jointly with Shietung Peng.

``Parallel Algorithms for Path Covering, Hamiltonian Paths, Hamiltonian Cycles Cograph'', 1990 International Conference on Parallel Processing, Vol.3 1990, 364-365, jointly with Shietung Peng.

IV. Papers Submitted to Refereed Journals:

0.

``On Asymptotic Complexity of Recurrences'', SIAM Journal of Computing, jointly with Arther B. Stephens and Shietung Peng.

``Algorithms for a k-core of a tree with applications'', Journal of Algorithms, jointly with Arther B. Stephens and Shietung Peng.

V. Invited Lectures :

0.

``Parallel Algorithms for K-trees and its Applications'', Invited lecture at the Computer Science Department, University of Umea, Sweden, Feb. 28 1994.

``Parallel Algorithms for Finding Connected, Independent, and Total Domination in Interval Graphs'', at the workshop on Parallel Algorithms and VLSI Architectures, June 3-6 1991, France.

``Parallel Algorithm for Maximum Matching in Cographs,'' at the Twenty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing, Florida Atlantic University, February 12-16, 1990.

``Parallel Algorithm for Cographs: Recognition and Applications'', at Algorithms and Data Structures Workshop WADS'89 Ottawa, Canada, August 16-18 1989.

International Conference on Computing and Information, Toronto, May 23-27 1989.

VI. Membership in professional societies:

0.

ACM Association for Computing Machinery (1986-present)

IEEE Computer Society (1986-present)

DECUS -Digital Equipment Corporation Users Society (1984-present)

MUG - MOSIS Users Group (1990 -present)

Upsilon Pi Epsilon - National Computer Science Honor Society (1991-present)