Past Projects

Northeast Parallel Architectures Center, Syracuse University, (July '93 - August '96)
- Parallel Algorithms for Coarse-grained Parallel Machines
  - Selection and Median Finding
    The selection problem is defined as follows: Given a set of N elements, a total order defined on the elements, and a number k, find the kth smallest element in the given set of elements. This research presents practical selection algorithms on coarse-grained parallel computers (e.g TMC CM-5, IBM SP2). Median finding is repeatedly used for constructing balanced binary trees.
  - Parallel Tree Construction
    k-d tree (or Multidimensional Binary Search Tree) is often used as a data structure for organizing and manipulating spatial data. In this research we present several algorithms for the parallel construction of k-d trees on coarse-grained distributed memory parallel machines (e.g TMC CM-5, IBM SP2).
  - Concatenated Parallelism
    A number of problems have efficient algorithms that are based on the divide and conquer paradigm. Such problems can be solved in parallel by mapping the corresponding divide and conquer tree to the parallel computer under consideration. Two basic strategies are used in such parallelizations: Task Parallelism, in which different subproblems are assigned to different groups of processors and Data Parallelism , in which tasks are solved one after the other using all the processors. We propose a new strategy, called Concatenated Parallelism which can be used for efficient parallel solution of problems when the data movement time in distributing the subproblems using task parallelism is significant when compared to the time required to divide the subproblems.
  - Related Publications:
    - Practical Algorithms for Selection on Coarse-Grained Parallel Computers,
      Ibraheem Al-furaih, Srinivas Aluru, Sanjay Goil and Sanjay Ranka,
      Proc. 10th International Parallel Processing Symposium (IPPS'96), 309-313, Honolulu, April 1996.
    - Practical Algorithms for Selection on Coarse-Grained Parallel Computers (long version),
      Ibraheem Al-furaih, Srinivas Aluru, Sanjay Goil and Sanjay Ranka,
      IEEE Transactions on Parallel and Distributed Systems 8 (8) (1997), 813-824.
    - Parallel Construction of Multidimensional Binary Search Trees,
      Ibraheem Al-furaih, Srinivas Aluru, Sanjay Goil and Sanjay Ranka,
      Proc. 10th International Conference on Supercomputing (ICS'96), 205-212, Philadelphia, May 1996.
    - Parallel Construction of Multidimensional Binary Search Trees (long version),
      Ibraheem Al-furaih, Srinivas Aluru, Sanjay Goil and Sanjay Ranka,
      IEEE Transactions on Parallel and Distributed Systems, To appear .
    - Concatenated Parallelism: A Technique for Efficient Parallel Divide and Conquer,
      Sanjay Goil, Srinivas Aluru and Sanjay Ranka,
      Proc. IEEE Symposium on Parallel and Distributed Processing (SPDP'96), 488-495, New Orleans, October 1996.
- PHANTOM - Parallelization of Hierarchical Applications and Treecodes On Multiprocessors
  In this research we address a class of problems consisting of highly structured computations on data sets that are described by hierarchical data structures. These are often represented as tree structures to optimize data storage requirements and perform efficient queries for data access. Specifically, applications that are dynamic and perform many iterations on data are of interest to us, since the requirements for data evolve over time and require modifying data structures incrementally. The computational relationship between the subdomains is known only at runtime, and may change between computation phases. Parallelization of such applications requires efficient distributed data management and has received some attention recently. We study the computational structure of a few irregular applications falling in this category. This helps us to evaluate data structures and the address issues of data partitioning, load balancing and communication requirements for these applications. Most recent efforts have been application specific and solutions are not portable across applications or parallel computing platforms. In this research we wish to characterize requirements for primitives and runtime software support needed to parallelize irregular applications.
  A study of the computational structure of applications allows us to identify requirements for parallelization across a broad spectrum. Each application uses a tree data structure to organize data for efficient construction, manipulation and querying of related data. We enumerate algorithms that are used for solving these applications and discuss their parallelization. We present an outline of primitives that are needed to parallelize such applications. These can be used to provide language support by high performance languages to parallelize hierarchical applications.
  - Related Publications:
    PHANTOM: Parallelization of Hierarchical Applications usiNg Treecodes On Multiprocessors,
    Sanjay Goil,
    Technical Report SCCS 773, Northeast Parallel Architectures Center, Syracuse University, August 1996.
AT&T Bell Laboratories, Murray Hill, NJ (August'91 - July'93)
- DiCE (Distributed Computing Environment) (January'93 - July'93)
  The goal is to construct a platform of multiprocessors to execute distributed applications. A high speed interface has been created for communication between the processors connected by the Sbus. The research issues are to partition the tasks among available resources to balance the load resulting in the minimum time of completion of the task. Circuit simulation is an application that has been implemented on the prototype hardware accelerator which can be implemented on this architecture with some modification. Communication is buffered on this fully connected network, and partitioning and scheduling algorithms are run in the initialization phase for task calculation and distribution.
- PACE: Parallel Architecture for Circuit Evaluation, (August '91 - December '92)
  This project is a research effort to accelarate the performance of ADVICE, AT&T's circuit simulator. This team developed a prototype 4 processor board with distributed memory running at 20 Mhz clock to run the code. This parallel architecture required some new algorithms for partitioning of the matrix for LU decomposition. A new measure of the ``earliest completion time'' was introduced by which the scheduling of the Normalize, Update and Back Sustitution tasks is done for the process of decomposition and sequencing the dependency of such tasks to establish the communication sequence between processors. This is the SOLVE of the matrix. The other important task is the LOAD , which is to establish the contribution of the circuit elements to the matrix, depending on it's connectivity. This task is also partitioned onto the processors using a partitioning schedule which optimizes the communication keeping the load on processors well balanced. Load balancing and minimum communication are two main issues involved in gaining reasonable speedups in performance.
- Related Publications:
  - Parallel Model Evaluation for Circuit Simulation on the PACE Multiprocessor,
    Prathima Agrawal, Sanjay Goil and John Trotter,
    The 7th International Conference on VLSI Design, Calcutta, January 1994.
  - PACE: A Multiprocessor System for VLSI Circuit Simulation,
    Sanjay Goil , Prathima Agrawal, Sally Liu and John Trotter,
    Proceedings of the SIAM Conference on Parallel Processing for Scientific Computing, Norfolk, Virginia, 1993.
Tata Consultancy Services, New Delhi, India (June '90 - July'91)
- Porting of UNIX System V Release 4.0 on different hardware platforms. (March'91 - July'91)
- Help Desk and Automated Release System for Overseas System support of Midland Bank on IBM AS400 (January'91-March'91)
- Automatic Generation of Cybernetic Influence Diagrams using Windows 3.1 SDK. (July'90-December'90)
Expert Software Consultants, New Delhi, India (June '89 - December'89) - Final semester training.
- Developing primitives for a English/Hindi bilingual system
- Multiprocessor locking mechanism at data level using shared memory.
Space Applications Center, Ahmedabad, India (Summer 1987)
- Porting of image processing and enhancement software from VAX 11/780 to PC platforms.