Login

Publications  •  Project Statistics

Glossary  •  Schools  •  Disciplines
People Search: 
   
Title/Abstract Search: 

Dissertation Information for Sekharipuram Subramaniam Ravi

NAME:
- Sekharipuram Subramaniam Ravi

DEGREE:
- Ph.D.

DISCIPLINE:
- Computing Science

SCHOOL:
- University of Pittsburgh (USA) (1984)

ADVISORS:
- None

COMMITTEE MEMBERS:
- None

MPACT Status: Incomplete - Not_Inspected

Title: HEURISTICS FOR PLA FOLDING: AN ANALYTICAL APPROACH

Abstract: "In this thesis, we examine a practical problem which arises in the automatic design and layout of Programmable Logic Arrays (PLA's). Folding is a technique used to reduce the area of PLA's. The problem of folding a PLA to its smallest possible area is known to be NP-Complete. The practical importance of this problem motivates the study of heuristics. So far, much of the work on heuristics for this problem has been of an experimental nature. We carry out an analytical study of heuristic algorithms for this problem.

The performance measure used to evaluate a heuristic (referred to as the folding ratio of the heuristic) is the worst case ratio of the optimal value to the value produced by the heuristic. We begin by determining the performance of several practical and intuitively appealing heuristics. These results show that for each of these heuristics, the folding ratio is unbounded. Next, we address the question of whether a constant folding ratio can be obtained in polynomial time. With respect to this question, we prove that three variants of the optimal folding problem are equivalent, in the sense that we can either obtain constant folding ratios in polynomial time for all the three variants or for none of them. We then prove, for one of these variants, that if there is a polynomial time heuristic whose folding ratio is some constant, then we can devise a polynomial time heuristic whose folding ratio is arbitrarily close to 1. These results indicate very strongly that no polynomial time approximation algorithm can guarantee a constant worst case ratio for an arbitrary PLA. However, for restricted classes of PLA's we show that constant ratios can be obtained in polynomial time. Finally, we address a variant of the folding problem (the orderability problem) and present some new results."

MPACT Scores for Sekharipuram Subramaniam Ravi

A = 0
C = 1
A+C = 1
T = 0
G = 0
W = 0
TD = 0
TA = 0
calculated 2008-01-31 06:13:26

Advisors and Advisees Graph