Prithviraj Banerjee - US grants

Researchers at the University of Illinois-Urbana will purchase a hypercube multiprocessor. The equipment will be used for research in computer science, including the following three research projects: (1) Design and implementation of sophisticated computer-aided design tools for VLSI that can run efficiently on the Hypercube multiprocessor. Specifically, tools will be developed for cell placement, wire routing, timing, logic and fault simulation, circuit extraction from mask layouts, and automatic test generation. (2) Intelligent heuristic searches for artificial intelligence applications. Strategies for parallel processing of heuristic searches on the Hypercube will be developed. Also to be considered will be program restructuring for parallel evaluation of logic programs. (3) Performance evaluation of the Hypercube system.

The availability of low-cost, high-density, high-speed processors and memories in VLSI, together with the increasing demands for high-performance in signal processing, has resulted in numerous proposals for highly parallel signal processing architectures. Since reliability is a key requirement, this research addresses the issues involved in the design of fault tolerance features in these parallel architectures. The specific, unique and promising approach to fault tolerance in this project is the use of low- cost on-line system-level error detection and correction techniques, which are tailored to the signal processing algorithms being executed on these architectures. Novel encoding schemes for various classes of signal processing algorithms are being explored. The effects of mapping large problems on limited processor mesh-connected architectures are being investigated from the viewpoint of algorithm-based checking. The effects of finite precision arithmetic on system level encodings are being studied. The fault coverage and reliability improvements due to algorithm-based checking schemes are being investigated using analytical techniques as well as functional simulations. Eventually, the research should result in the identification of some basic principles for the design of algorithm-based fault tolerance techniques.

The focus of Dr. Banerjee's work is VLSI CAD tools which run on a class of message-passing architectures, such as hypercubes. In this research he will investigate algorithms for tools which perform the task of circuit extraction from VLSI mask layouts. The technical approach is to flatten the hierarchical description into a mask description consisting of rectangles, and perform the extraction at this level. The new multiprocessor algorithms will be used for speedup and accurate, fast-circuit extraction. The algorithms will use region queries in parallel on a data structure distributed over the parallel processor. It is anticipated that this procedure will avoid the boundary effect problems that may arise when splitting a VLSI layout area into regions.

This research is on developing circuit design and test algorithms that run on parallel computers. These include efficient, asynchronous, portable parallel algorithms for: (A) synthesis of combinational circuits; and (B) for test generation and fault simulation of combinational and sequential circuits. Algorithms are being written using an environment that makes it possible to port CAD applications across a wide range of MIMD machines. In addition they are designed to allow a maximum overlap of computation and communication. The algorithms are being tested on numerous parallel platforms.

Distributed-memory, massively-parallel multicomputers can provide the high levels of performance required to solve the Grand Challenge computational science problems. Multicomputers offer significant advantages over shared- memory multiprocessors in terms of cost and scalability. Unfortunately, extracting all the computational power from these machines requires users to write efficient software for them, which is an extremely laborious and error-prone process. The distribution of data across processors is of critical importance to the efficiency of the parallel program in a distributed memory system. In this project the problem of automated data distribution in such machines is being investigated. The approach is unique in that it is based on sophisticated cost models of communication and computation that are parameterized by architectural metrics empirically measured for different target machines. Using the cost estimates, data distributions are selected to minimize the overall execution time of the program by maximizing parallelism (while maintaining load balance) and minimizing the amount of communication overhead (by maximizing data locality). Both static and dynamic distribution will be supported in a unified framework to automatically select data distributions which can dynamically change over the course of a program's execution in order to provide scalable parallel performance for large, complex applications. This approach not only has a solid theoretical basis, but is being integrated into a sophisticated compiler which can actually generate code for a variable number of processors supporting all block, cyclic, and block-cyclic data distributions. The compilation techniques investigated in this project will also be integrated with simultaneous support for regular and irregular accesses in parallel applications through a novel interval-based representation. ***

CDA-9703228 Prithviraj Banerjee Northwestern University A Distributed High-Performance Computing Infrastructure This award is for the acquisition of 20 high-end UNIX workstations, 50 low-end UNIX workstations, three UNIX fileservers, an 8-processor distributed shared memory multiprocessor, and a 64-ported ATM switching hub. The machines would be networked together using high-speed OC-3 ATM networks with bandwidths of 155 Mbps. As the use of high-speed networking moves from the laboratory to the workplace, new opportunities arise for the design and implementation of a high-speed distributed computing environment. The goals of this project are: (1) to explore the use of high-speed networking and computing to investigate file systems and data management issues for high-performance distributed computing, (2) to investigate the parallel programming support of networks of high-speed workstations and personal computers as an alternative to stand-alone parallel computers, (3) to study high-performance computer-aided design of electronic systems in a heterogeneous environment, and to develop a Web-based CAD computing center, that takes advantage of high-speed networking, (4) to explore new instructional techniques that take advantage of the high bandwidth and high speed.

EIA 02-24449
Dinda, Peter A.
Banerjee, Prithviraj; Kao, Ming-Yang
Northwestern University

CISE RR: Collaborative Research on Wide-Area Network Computing Using Virtual Machines
This collaborative research project (with Fortes at University of Florida, proposal 02-24442), requiring a wide-area test bed that enables experimentation with, access to, and running of applications on unique resources, requests PC clusters, an IBM server, and other ancillary hardware for projects in
1. Distributed grid computing and information processing systems using virtualization technologies and
2. Information grids with real users and research applications requiring capabilities enabled by virtual machines (VMs).
Deploying a distributed system based on clusters connected by local, metropolitan, and wide area networks, the work aims to provide a virtual computing and data storage interface to clients that access resources on the underlying "information grid." The test bed includes the following defining features.
1. Virtualization capabilities, i.e., the ability to instantiate independent logical machines that can be multiplexed on physical processors (or fractions of them), storage and network I/O channels, and can use distinct operating systems;
2. Wide-area distribution, i.e., Internet-linked test bed components in independently-administered geographically-apart network domains;
3. Scalable capacity for both scientific computing and information processing; and
4. Heterogeneity.
Interrelated projects enabled by the test bed towards the goal of developing VM-based middleware for grid computing include virtualized end resources, monitoring and prediction, interactive computing, virtual file systems, data management, cycle selling, and security. Information grids and web portals for use of CAD tools are also enabled by the infrastructure for dissemination of collaborative research results and data, and for digital government services. From the availability of the portals and grid-computing resources benefits are expected in brain-machine interfaces, biologically-inspired nanocomputing, auction-based computing, distributed knowledge applications, medical imaging and data archiving, light-scattering spectroscopy, and mixed non-linear optimization. Collaborations include the Sigmicro microarchitecture center, NETCARE and the Purdue-hosted Nanohub (enabling users to run tools for computer architecture and parallel computing, and nanoelectrnics). The project impacts some minority serving institutions such as Chicago State and Florida A& M Universities and enables a testbed for a transnational digital government projects involving Carnegie Mellon University, University of Belize, University of Colorado, University of Florida, University of Massachusetts, and Pontificia Universidad Catolica Madre y Maestra of the Dominican Republic.

The goal of the Women in Science and Engineering System Transformation (WISEST)
project, at the University of Illinois at Chicago (UIC), is to increase the number, participation,
and leadership status of women, majority and minority, in eleven science and engineering
(STEM) departments through institutional transformation. WISEST will use an innovative
approach of a network of faculty facilitators from all STEM departments working with
department heads and an executive committee of key administrators and a social scientist.
This network will carry out five integrated and mutually reinforcing strategies: warm the
climate and decrease the isolation of women STEM faculty; recruit minority women faculty
through an unique mentored postdoctoral program; transform STEM departments to foster
diversity and womens leadership; promote womens scholarship and teaching; and improve
the ability to track and report on gender equity. Proposed outcomes for STEM women
faculty include: increased numbers of majority and minority faculty; improved retention
rate; salary equity with men of similar accomplishments and productivity; increased
percentage of leadership positions; improved job satisfaction; and increased national visibility
for our scholars. The intellectual merit of WISEST is that it will assess the impact of
systemic change to erase gender stereotyping rather than individual remediation and it will
specifically extend the focus of action to include the postdoctoral level to recruit faculty. Its
broader impact will be the creation of a life-friendly work climate for all UIC faculty.
WISEST will share its experiences nationally, and serve as an exemplary model for fostering
gender equity and diversity in academe.