NANA 2 - 6632
Work Area: Algorithms for Design Methodologies for Complex Circuits and Digital Optical Systems
Keywords parallel algorithms, real-time multi-dimensional signal and data processing, parallel application specific architectures and synthesis techniques
Start Date: 1 June 92 / Duration: 36 months / Status: running
[ participants / contact ]
Abstract Novel parallel algorithms, VLSI architectures and synthesis techniques for the important domain of multidimensional signal processing (MDSP) are badly needed in real-time systems. Their development will have a beneficial impact on computer-aided hardware design and synthesis environments. The work builds on the results of NANA (action 3280).
Aims
A first aim of NANA 2 is to develop new real-time parallel algorithms and new VLSI architectures for a variety of applications, both in real-time multi-dimensional signal processing and in numerical processing. Here, a clear need exists for novel parallel algebraic and numerical kernels and the combinations of kernels into complete algorithms.
In order to allow future design of complex high throughput applications, NANA 2 also explores novel technologies in the area of architectural synthesis techniques, which create a suitable architecture from a behavioural specification.
Approach and Methods
The NANA 2 approach will continue on the same track as that of NANA (action 3280), with the work divided into two areas:
- Novel algorithms for parallel architectures. These algorithms will be developed for time-critical and/or space-critical practical problems. NANA2 will emphasise a class of sophisticated algorithms which combine several submodules. In this way, the approach is better targeted to complete applications, compared to NANA.
- New architectural design methodologies and synthesis techniques : appropriate subsets of architectural features, ie specific "target architectural styles" will be selected, depending on the application field in mind. The different novel algorithms to be developed have specific characteristics which can be matched with specific features in different architectural styles. Several basic transformations, common to all synthesis techniques, will be studied. At the same time some prototype synthesis tools will be developed, loosely coupled in a common work-bench approach.
Progress and Results
The following major results have been achieved:
- ENSL has designed and implemented new algorithms for rendering and for skeletonisation. They have also investigated scheduling techniques for loop nests with uniform or affine dependences.
- ESAT has proposed practical parallel recursive updating algorithms for adaptive antenna applications, namely robust linearly constrained minimum variance beamforming and direction-of-arrival estimation for multiple wide-band emitters.
- Delft has completely generalised the Hankel-norm approximation problem in the context of model reduction to the time-varying case. They have also realised a parallel-pipelined multiprocessor system for the rendering of photo realistic scenes in interaction time. Finally, the implementation of the HIFI design tools has been extended.
- INRIA has completed the study and implementation of several new transformations in the Alpha array synthesis environment, including the link to VLSI chip generation. Alpha is now also available under Mathematica.
- IMEC has coupled their memory optimisation techniques to a behavioural simulator, resulting in significant simulation speed-ups. Also the models used for memory management have been extended towards variable-rate image processing applications.
All these developments have lead to several publications in international journals and conferences, and to 6 Ph.D. dissertations. Based on these results, we believe the project to be very successful up to now. All milestones have been achieved and all planned deliverables have been produced.
Potential
The work is of major importance for the development of efficient systems in many fields such as image and seismic processing, video, robotics, radar, sonar, telecommunication, factory automation, biomedical technology and adaptive beamforming. Studying the systems in terms of both novel parallel algorithms and efficient new architectural methodologies will allow to map these systems onto future VLSI or parallel processor realisations with smaller design and production costs.
Latest Publications
Most recent results for the domains addressed in this project have been published in a large number of articles in international conferences, workshops and journals. Major articles include:
- Darte A, Risset T, Robert Y Loop nest scheduling and transformations In: Environments and Tools for Parallel Scientific Computing, Dongarra J J et al. (eds.), Advances in Parallel Computing 6, North Holland, Amsterdam, pp.309-332 (1993)
- Moonen M, Van Dooren P, Vandewalle J A systolic array for SVD updating SIAM J. Matrix Anal. Appl., Vol. 14, No. 2, pp 353-371 (1993)
- Deprettere E F, Held P, Wielage P Model and methods for regular array design Int. Journal of High Speed Electronics and Systems, Special issue on Massively Parallel Computing - part 2 (1993)
- Charot F, Frison P, Gautrin E, Lavenier D, Quinton P and Wagner C From equations to hardware. Towards the systematic mapping of algorithms onto parallel architectures In: Second International Conference on Parallel Image Analysis, Ube, Japan, submitted to a Special Issue of the International Journal of Pattern Recognition and Artificial Intelligence (1992)
- Franssen F, Balasa F, van Swaaij M, Catthoor F, De Man H Modelling Multi-Dimensional Data and Control flow IEEE Trans, on VLSI systems, (1993)In addition, a book has been assembled which contains overview chapters related to the parallel architecture and methodology work of the NANA 2 partners: Catthoor F, Svensson L (eds.) Application-driven architecture synthesis, Kluwer, Boston (1993).
Information Dissemination Activies
Several internal mini-workshops have been organised, where the partners have exchanged information, also including many researchers which are not on the NANA2 budget. A global international workshop will be organised which is open to the academic and industrial community. The target location is Leuven and the target date is May 1994.
Several partners are also spending effort in industrial affiliate and other industrial programmes to disseminate early successes of the NANA 2 work.
Coordinator
IMEC vzw - B
Kapeldreef 75
B - 3001 LEUVEN
Partners
Katholieke Universiteit Leuven - B
Ecole Normale Supérieure de Lyon - F
INRIA/IRISA - F
Delft University of Technology - NL
CONTACT POINT
Prof. Francky Catthoor
tel +32/16 281201
fax +32/16 281515
e-mail: catthoor@imec.be (UUCP)
NANA 2 - 6632, August 1994
please address enquiries to the ESPRIT Information Desk
html version of synopsis by Nick Cook