Sponsor:

• DoD Modernization Program

---

Project Team Members:

Northwestern University

• Alok Choudhary
• Wei-keng Liao

Syracuse University

• Prof. Donald Weiner
• Prof. Pramod Varshney

Air Force Research Labs

• Dr. Richard Linderman
• Dr. Mark Linderman

---

• Objectives • Problem Description • Methodology • Project Overview • Performance Results • Significance • Publications • Conference Talk Slides • Reference •

---

Design, Implementation and Evaluation of Parallel Pipelined Space-Time Adaptive Processing on Parallel Computers

---

Objectives:

To design, implement and evaluate computationally intensive signal processing applications on high-performance parallel embedded systems. As part of this project, we have developed and deployed techniques for parallelization, task mapping and allocation, parallel pipelined communication, data redistribution for applications consisting of several tasks. Another important goal of this project is to achieve a balance of throughput and latency through optimal use of the finite computational resources.

Problem Description:

Applications such as STAP entail multiple algorithms (or processing steps), each of which performs particular functions, to be executed in a pipelined fashion. Multiple pipelines need to be executed in a staggered manner to satisfy the throughput requirements. Each task needs to be parallelized for the required performance, which, in turn, requires addressing the issue of data distribution on the subset of processors on which a task is parallelized to obtain good efficiency and incur minimal communication overhead. Given that each task is parallelized, data flow among multiple processors of two or more tasks is required and, therefore, communication scheduling techniques become critical.

Methodology:

We have completed an implementation of the Rome Labs PRI-Staggered Space-Time Adaptive Processing (STAP) application. This STAP algorithm involves (1) Doppler filter processing, (2) weight computation, (3) beam forming, (4) pulse compression, and (5) CFAR processing. We designed a model of parallel pipeline system for the type of STAP applications, shown in Figure 1. The pipeline is a collection of tasks and each task itself is parallelized. The implementation is portable across different parallel machines.

Figure 1. Implementation of parallel pipelined STAP. Arrows connecting task blocks represent data transfer between tasks.

Project Overview:

Current research topics in the project have been focused in the following areas:

• Modeling the parallel pipeline system
  • Inter-task data redistribution
  • Task scheduling and processor assignment
• Multi-threading implementation on Intel Paragon SMP nodes

Performance Results:

• On Intel Paragon XP/S at Air Force Research Laboratory (AFRL) in Rome, New York
• On IBM SP at Argonne National Laboratory
• On SGI Origin at Northwestern University

Significance:

Given that the STAP application that is parallelized is one of the few used in the DoD (Rome Laboratory has successfully implemented this STAP algorithm on-board an airborne platform), and is one of the most computationally intensive signal processing algorithm with complex data and communication patterns, our project has demonstrated that techniques developed as part of this project are important and high-performance parallel computers can provide significant performance benefits for such applications.

Publications:

1. Wei-keng Liao, Alok Choudhary, Donald Weiner, and Pramod Varshney. Performance Evaluation of a Parallel Pipeline Computational Model for Space-Time Adaptive Processing. Journal of Supercomputing, 31(2):137–160, February 2005. (unavailable)
2. Wei-keng Liao, Alok Choudhary, Donald Weiner, and Pramod Varshney. Design and Evaluation of I/O Strategies for Parallel Pipelined STAP Applications. In Proceedings of the 14th International Parallel and Distributed Processing Symposium (IPDPS), pp. 655–662, May 2000.(pdf) 
3. Alok Choudhary, Wei-keng Liao, Donald Weiner, Pramod Varshney, Richard Linderman, Mark Linderman, and Russel Brown. Design, Implementation and Evaluation of Parallel Pipelined STAP on Parallel Computers. IEEE Transactions on Aerospace and Electronic Systems (TAES), 36(2):528–548, April 2000.(pdf) 
4. Wei-keng Liao, Alok Choudhary, Donald Weiner, and Pramod Varshney. Multi-Threaded Design and Implementation of Parallel Pipelined STAP on Parallel Computers with SMP Nodes. In Proceedings of the 13th International Parallel Processing Symposium / 10th Symposium on Parallel and Distributed Processing (IPPS/SPDP), pp. 448–452, April 1999.(pdf) 
5. Alok Choudhary, Wei-keng Liao, Donald Weiner, Pramod Varshney, Richard Linderman, and Mark Linderman. Design, Implementation and Evaluation of Parallel Pipelined STAP on Parallel Computers. In Proceedings of the 12th International Parallel Processing Symposium / 9th Symposium on Parallel and Distributed Processing (IPPS/SPDP), pp. 220–225, March 1998.(pdf) 

Conference talk slides:

1. International Conference on HiPC 1999 (ps.gz)
2. IPPS/SPDP 1999 (ps.gz)
3. IPPS/SPDP 1998 (ps.gz)
4. DoD User Group Meeting 1997 (ps.gz)

Reference:

1. R. Brown and R. Linderman, "Algorithm Development for an Airborne Real-Time STAP Demonstration", IEEE National Radar Conference, 1997.
2. M. Linderman and R. Linderman, "Real-Time STAP Demonstration on an Embedded High Performance Computer", IEEE National Radar Conference, 1997.
3. M. Little and W. Berry, "Real-Time MultiChannel Airborne Radar Measurements", IEEE National Radar Conference, 1997.