We propose a post-placement physical synthesis algorithm that can apply multiple circuit synthesis and placement transforms on a placed circuit to improve the critical path delay under area...
Research Accomplishments (2009)
My research areas include VLSI CAD, FPGA testing and trust design, fault-tolerant computing and parallel processing. We have also made a recent foray into optimization. Our work has received one best...
A novel trust-based design method for FPGA circuits that uses error-correcting code (ECC) structures for detecting design tampers—changes, deletion of existing logic, and addition of extradesign...
A Network-Flow Approach to Timing-Driven Incremental Placement for ASICs (2008)
Shantanu Dutt, Huan Ren, Fenghua Yuan, Vishal Suthar
We present a novel incremental placement methodology called FlowPlace for significantly reducing critical path delays of placed standard-cell circuits. FlowPlace includes: a) a timing-driven (TD)...
Mixed PLB and Interconnect BIST for FPGAs without Fault-Free Assumptions (2008)
Abstract We tackle the problem of fault-free assumptions in current PLB and interconnect built-in-self-test (BIST) techniques for FPGAs. These assumptions were made in order to develop strong BIST...
Shantanu Dutt, Vinay Verma, Vishal Suthar
Abstract — We present novel and efficient methods for builtin-self-test (BIST) of FPGAs for detection and diagnosis of permanent faults in current as well as emerging technologies that are expected...
Off-Chip Control Flow Checking of On-Chip Processor-Cache Instruction Stream ∗ (2008)
Federico Rota, Shantanu Dutt, Sahithi Krishna
Control flow checking (CFC) is a well known concurrent checking technique for ensuring that a program’s instruction execution sequence follows permissible paths. Almost all CFC techniques require...
Technical Report Probability-Based Approaches to VLSI Circuit Partitioning (2008)
Iterative-improvement 2-way min-cut partitioning is an important phase in most circuit placement tools. It is also used for other CAD applications like multiple-chip/FPGA implementation of large...
A Network-Flow Based Cell Sizing Algorithm (2008)
Abstract—We propose a timing-driven discrete cellsizing algorithm that can incorporate total cell size constraints. We model cell sizing as a min-cost network flow problem. In the network flow...
An Accurate and Stochastic-Based Approach to Timing-Driven Partitioning and Placement (2007)
We present an accurate new approach to timing-driven partitioning and placement that is particularly suited to deep submicron technology, and to the large circuits that are implemented on such chips....
A Search-Based Bump-and-Refit Approach to Incremental Routing for ECO Applications (2007)
In Fpgas, Shantanu Dutt, Vinay Verma, Hasan Arslan
Incremental physical CAD is encountered frequently in the so-called engineering change order (ECO) process in which design changes are made typically late in the design process in order to correct...
An Efficient Delay-Optimal Distributed Termination Detection Algorithm. To Appear (2004)
Nihar R. Mahapatra, Shantanu Dutt
One of the important issues to be addressed when solving problems on parallel machines or distributed systems is that of ecient termination detection. Numerous schemes with dierent performance...
Efficient On-line Testing of FPGAs with Provable Diagnosabilities (2004)
Vinay Verma, Shantanu Dutt, Vishal Suthar
We present novel and efficient methods for on-line testing in FPGAs. The testing approach uses a ROving TEster (ROTE), which has provable diagnosabilities and is also faster than prior FPGA testing...
An Efficient Delay-Optimal Distributed Termination Detection Algorithm. To Appear (2004)
Nihar R. Mahapatra, Shantanu Dutt
One of the important issues to be addressed when solving problems on parallel machines or distributed systems is that of efficient termination detection. Numerous schemes with different performance...
We have developed a hop-based complete detailed router ROAD-HOP that uses the Bump & Refit ( ) approach to route a FPGA circuit in a near-optimal manner. This approach is based on generating a...
A Search-Based Bump-and-Refit Approach to Incremental Routing for ECO Applications in FPGAs (2002)
Abstract: Incremental physical CAD is encountered frequently in the socalled engineering change order (ECO) process in which design changes are made typically late in the design process in order to...
Cluster-Aware Iterative Improvement Techniques for Partitioning Large VLSI Circuits (2002)
this paper, we propose a technique CLIP (CLuster-oriented Iterative-improvement Partitioner) that significantly improves the ability of IIP methods like FM and LA to find good local minima. The new...
Effective partition-driven placement with simultaneous level processing and global net views (2000)
Abstract: In this paper we take a fresh look at the partition-driven placement (PDP) paradigm for standard-cell placement for wire-length minimization. The goal is to develop several new algorithms...
Efficient Network-Flow Based Techniques for Dynamic Fault Reconfiguration in FPGAs (1999)
Nihar R. Mahapatra, Shantanu Dutt
In this paper, we consider a "dynamic " node covering framework for incorporating fault tolerance in SRAM-based segmented array FPGAs with spare row(s) and/or column(s) of cells....
Efficient Incremental Rerouting for Fault Reconfiguration (1999)
Shantanu Dutt, Vimalvel Shanmugavel, Steve Trimberger
Abstract The ability to reconfigure around manufacturing defects and operational faults increases FPGA chip yield, reduces system downtime and maintenance in field operation, and increases...
Sequential and Parallel Branch-and-Bound Search Under Limited-Memory Constraints (1999)
Nihar R. Mahapatra, Shantanu Dutt
Branch-and-bound (B&B) best-first search (BFS) is a widely applicable method that requires the least number of node expansions to obtain optimal solutions to combinatorial optimization problems...
Efficient Network-Flow Based Techniques for Dynamic Fault Reconfiguration in FPGAs (1999)
Nihar R. Mahapatra, Shantanu Dutt
In this paper, we consider a “dynamic ” node covering framework for incorporatingfault tolerance in SRAM-based segmented array FPGAs with spare row(s) and/or column(s) of cells. Two types of...
Methodologies for Tolerating Cell and Interconnect Faults in FPGAs (1998)
Abstract—The very high levels of integration and submicron device sizes used in current and emerging VLSI technologies for FPGAs lead to higher occurrences of defects and operational faults. Thus,...
Nihar Mahapatra And, Nihar R. Mahapatra, Shantanu Dutt
In this paper, we present an adaptive version of our previously proposed quality equalizing (QE) load balancing strategy that attempts to maximize the performance of parallel branch-and-bound...
Methodologies for Tolerating Cell and Interconnect Faults in FPGAs (1998)
The very high levels of integration and submicron device sizes used in current and emerging VLSI technologies for FPGAs lead to higher occurrences of defects and operational faults. Thus, there is a...
Partitioning Using Second-Order Information and Stochastic-Gain Functions (1998)
A probability-based partitioning algorithm, PROP, was introduced in [5] that achieved large improvements over traditional "deterministic" iterative-improvement techniques like FM [7] and LA...
Shantanu Dutt, Nihar R. Mahapatra
Abstract—Structural fault tolerance (SFT) is the ability of a multiprocessor to reconfigure around faulty processors or links in order to preserve its original processor interconnection structure....
Shantanu Dutt, Nihar R. Mahapatra
Abstract---Structural fault tolerance (SFT) is the ability of a multiprocessor to reconfigure around faulty processors or links in order to preserve its original processor interconnection structure....
Cluster-Aware Iterative Improvement Techniques • 121 (1997)
Move-based iterative improvement partitioning (IIP) methods, such as the Fiduccia-Mattheyses (FM) algorithm [11] and Krishnamurthy's Look-Ahead (LA) algorithm [15], are widely used in VLSI CAD...
Partitioning Around Roadblocks: Tackling Constraints with Intermediate Relaxations (1997)
The VLSI circuit partitioning problem with any given objective like mincut is inherently a constraint-driven one. Frequently encountered constraints range from specified balance-ratios on total cell...
A probability-based approach to VLSI circuit partitioning (1996)
Iterative-improvement 2-way min-cut partitioning is an important phase in most circuit placement tools, and finds use in many other CAD applications. Most iterative improvement techniques for circuit...
A Probability-Based Approach to VLSI Circuit Partitioning (1996)
Iterative-improvement 2-way min-cut partitioning is an important phase in most circuit partitioning tools. Most iterative improvement techniques for circuit netlists like the Fidducia-Mattheyses (FM)...
VLSI Circuit Partitioning by Cluster-Removal using Iterative Improvement Techniques (1996)
Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm [3] and Krishnamurthy's Look-Ahead (LA) algorithm [4] are widely used in VLSI CAD...
VLSI Circuit Partitioning by Cluster-Removal Using Iterative Improvement Techniques (1996)
Move-based iterative improvement partitioning (IIP) methods, such as the Fiduccia-Mattheyses (FM) algorithm [11] and Krishnamurthy's Look-Ahead (LA) algorithm [15], are widely used in VLSI CAD...
Nihar Mahapatra And, Nihar R. Mahapatra, Shantanu Dutt
We propose a completely general, informed randomized dynamic load balancing method called random seeking (RS) suitable for parallel algorithms with characteristics found in many search algorithms...
VLSI Circuit Partitioning by Cluster-Removal Using Iterative Improvement Techniques (1996)
Move-based iterative improvement partitioning methods such as the Fiduccia-Mattheyses (FM) algorithm [3] and Krishnamurthy's Look-Ahead (LA) algorithm [4] are widely used in VLSI CAD...
A probability-based approach to VLSI circuit partitioning (1996)
Iterative-improvement 2-way min-cut partitioning is an important phase in most circuit placement tools, and finds use in many other CAD applications. Most iterative improvement techniques for circuit...
Nihar R. Mahapatra, Shantanu Dutt
For many applications of the A* algorithm, the state space is a graph rather than a tree. The implication of this for parallel A* algorithms is that different processors may perform significant...
New Anticipatory Load Balancing Strategies for Parallel A* Algorithms (1995)
Nihar Mahapatra Shantanu, Shantanu Dutt
In this paper, we develop load balancing strategies for scalable highperformance parallel A* algorithms suitable for distributed-memory machines. In parallel A* search, inefficiencies such as...
Scalable Load Balancing Strategies for Parallel A* Algorithms (1994)
Shantanu Dutt, Nihar R. Mahapatra
In this paper, we develop load balancing strategies for scalable high-performance parallel A* algorithms suitable for distributed-memory machines. In parallel A* search, inefficiencies such as...
Parallel A* Algorithms and their Performance on Hypercube Multiprocessors (1993)
Shantanu Dutt Member, Shantanu Dutt, Member Ieee, Nihar R. Mahapatra, Student Member Ieee
In this paper we develop parallel A* algorithms suitable for distributed-memory machines. In parallel A* algorithms, inefficiencies grow with the number of processors P used, causing performance to...
Scalable Duplicate Pruning Strategies for Parallel A* Graph Search (1993)
Nihar Mahapatra Shantanu, Shantanu Dutt
In parallel A* graph search on distributed-memory machines, different processors may perform significant duplicated work if inter-processor duplicates are not pruned. The only known method for...
New Faster Kernighan-Lin-Type Graph-Partitioning Algorithms (1993)
: In this paper we present a very efficient graph partitioning scheme Quick Cut that uses the basic strategy of the Kernighan-Lin (K-L) algorithm to swap pairs of nodes to improve an existing...
Designing fault-tolerant systems using automorphisms (1991)
Dutt, Shantanu, Hayes, John P.
This paper presents a general theory for modeling and designing fault-tolerant multiprocessor systems in a systematic and efficient manner. We are concerned here with structural fault tolerance,...
Designing and reconfiguring fault-tolerant multiprocessor systems / (1990)
Thesis (Ph. D.)--University of Michigan, 1990.
DESIGNING AND RECONFIGURING FAULT-TOLERANT MULTIPROCESSOR SYSTEMS (FAULT TOLERANCE). (1990)
This thesis presents a general theory for designing multiprocessor computer systems that can tolerate faulty processors. It is especially concerned with structural fault tolerance, defined as the...
An Efficient Delay-Optimal Distributed Termination Detection Algorithm
Nihar R. Mahapatra, Shantanu Dutt
One of the important issues to be addressed when solving problems on parallel machines or distributed systems is that of efficient termination detection. Numerous schemes with different performance...