A C-type class of mixed river routings

Author

John Charles Dempsey

Date of Award

8-1994

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Jean R.S. Blair

Committee Members

Heather Booth, Michael Langston

Abstract

Previous work on the river routing problem yielded three successively larger classes of routings: internal, internal-external, and mixed. In this paper we con- sider a larger class of mixed routings which uses C-type mixed wires with jogs, as well as C-type cut throughs, to generate further reductions in vertical density and overall area. By starting with an optimal mixed routing, and selectively inserting C-type mixed wires with jogs, a new routing is generated which is potentially more compact than the optimal mixed, yet it retains the same channel width and markings of the nets. An O(n²) algorithm is presented for creating routings in this new C-type mixed class which utilize as many C-type mixed wires as possible without changing the net markings.

Recommended Citation

Dempsey, John Charles, "A C-type class of mixed river routings. " Master's Thesis, University of Tennessee, 1994.
https://trace.tennessee.edu/utk_gradthes/11510