Pipelined ProcessorFarms
WILEY
SERIES
ON PARALLEL
AND DISTRIBUTED
COMPUTING
Series Editor: Albert Y. Zomaya Para...
238 downloads
1425 Views
11MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Pipelined ProcessorFarms
WILEY
SERIES
ON PARALLEL
AND DISTRIBUTED
COMPUTING
Series Editor: Albert Y. Zomaya Parallel
and Distributed
Simulation
Systems
Surviving the Design of Microprocessor Lessons Learned / Veljko Milutinovic Mobile
Processing
Introduction Solutions Biological
in Distributed
to Parallel
/ Richard Fujimoto
and Multimicroprocessor
and Open Environments
Algorithms
/ Peter Sapaty
/ C. Xavier and S. S. lyengar
to Parallel and Distributed Computing Problems: Lessons from Sciences / Albert Y. Zomaya, Fikret Ercal, and Stephan Olariu (Editors)
New Parallel Algorithms for Direct Solution of Linear Equations Murthy, K. N. Balasubramanya Murthy, and Srinivas Aluru Practical PRAM Programming Jesper Larsson Traeff Computational
Collective
/ Joerg Keller, Christoph
Intelligence
/ Tadeusz
A Survey of Models,
Fundamentals of Distributed Zahir Tari and Omran Bukhres
Systems:
Object
Processor Farms: Structured Design / Martin Fleury and Andrew Downton
/ C. Siva Ram
Kessler, and
M. Szuba
Parallel and Distributed Computing: Approaches / Claudia Leopold
Pipelined Systems
Systems:
A CORBA
Paradigms,
Perspective
for Embedded
Parallel
and
/
Pipelined ProcessorFarms Structured Design for Embedded Parallel Systems
Martin Andrew
Fleury
Downton
A Wiley-Interscience
JOHN New York
/ Chichester
/ Weinheim
WZLEY&
/ Brisbane
Publication
SONS,
/ Singapore
INC.
/ Toronto
This text is printed
on acid-free
paper. @
Copyright
0 2001 by John Wiley & Sons, Inc. All rights reserved.
Published
simultaneously
in Canada.
No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 0 1923, (978) 750-8400, fax (978) 750-4744. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 605 Third Avenue, New York, NY 10158-0012, (212) 850-6011, fax (212) 850-6008, E-Mail: PERMREQ @ WILEY.COM. For ordering Library
and customer
of Congress
service,
Cataloging
ISBN O-471-22438-3 This title is also available
call I-800-CALL-WILEY.
in Publication
in print as ISBN o-471-38860-2.
Printed in the United States of America 10987654321
Data is available.
Foreword
Parallel systems are typically difficult to construct, to analyse, and to optimize. One way forward is to focus on stylized forms. This is the approach taken here, for Pipelined Processor Farms (PPF). The target domain is that of embedded systems with continuous flow of data, often with real-time constraints. This volume brings together the results of ten years study and development of the PPF approach and is the first comprehensive treatment beyond the original research papers . The overall methodology is illustrated throughout by a range of examples drawn from real applications. These show both the scope for practical application and the range of choices for parallelism both in the pipelining and in the processor farms at each pipeline stage. Freedom to choose the numbers of processors for each stage is then a key factor for balancing the system and for optimizing performance characteristics such as system throughput and latency. Designs may also be optimized in other ways, e.g. for cost, or tuned for alternative choices of processor, including future ones, providing a high degree of future-proofing for PPF designs.
vi
FOREWORD
An important aspect is the ability to do “what if’ analysis, assisted in part by a prototype toolkit, and founded on validation of predicted performance against real. As the exposition proceeds, the reader will get an emerging understanding of designs being crafted quantitatively for desired performance characteristics. This in turn feeds in to larger scale issues and trade-offs between requirements, functionality, benefits, performance, and cost. The essence for me is captured by the phrase “engineering in the performance dimension”. CHRIS WADSWORTH
TECHNICALCO-ORDINATOR EPSRC PROGRAMMEON PORTABLESOFTWARETOOLS FORPARALLEL ARCHITECTURES Wantage,
Nou..t?OQO
Preface
In the 198Os, the advent of the transputer led to widespread investigation of the potential of parallel computing in embedded applications. Application areas included signal processing, control, robotics, real-time systems, image processing, pattern analysis and computer vision. It quickly became apparent that although the transputer provided an effective parallel hardware component, and its associated language Occam provided useful low-level software tools, there was also a need for higher-level tools together with a systematic design methodology that addressed the additional design parameters introduced by parallelism. Our work at that time was concerned with implementing real-time document processing systems which included significant computer vision problems requiring multiple processors to meet throughput and latency constraints. Reviews of similar work highlighted the fact that processor farms were often favored as an effective practical parallel implementation architecture, and that many applications embodied an inherent pipeline processing structure. After analyzing a number of our own systems and those reported by others we concluded that a combination of the pipeline structure with a generalized processor farm implementation at each pipeline stage offered a flexible generalpurpose architecture for soft real-time systems. We embarked upon a major project, PSTESPA (Portable Software Tools for Embedded Signal Processing Applications) to investigate the scope of the Pipeline Processor Farm (PPF) design model, both in terms of its application potential and the supporting software tools it required. Because the project focused mostly upon high-level vii
... VI//
PREFACE
design issues, its outcome largely remains valid despite seismic changes within the parallel computing industry. By the end of our PSTESPA project, notwithstanding its successful outcome, the goalposts of parallel systems had moved, and it was becoming apparent that many of the ambitious and idealistic goals of general-purpose parallel computing had been tempered by the pragmatic reality of market forces. Companies such as Inmos, Meiko, Parsys and Parsytec (producing transputer-based machines), and ICL, AMT, MasPar and Thinking Machines (producing SIMD machines), found that the market for parallel applications was too fragmented to support high-volume sales of large-scale parallel machines based upon specialized processing elements, and that application development was slow and difficult with limited supporting software tools. Sharedmemory machines produced by major uniprocessor manufacturers such as IBM, DEC, Intel and Silicon Graphics, and distributed Networks of Workstations (NOWs) had however established a foothold in the market, because they are based around high-volume commercial off-the-shelf (COTS) processors, and achieved penetration in markets such as database and file-serving where parallelism could be supported within the operating system. In our own application field of embedded systems, NOWs and sharedmemory machines have a significant part to play in supporting the parallel logic development process, but implementation is now increasingly geared towards hardware-software co-design. Co-design tools may currently be based around heterogeneous computing elements ranging from conventional RISC and DSP processors at one end of the spectrum, through embedded processor cores such as ARM, to FPGAs and ASICs at the other. Historically, such tools have been developed bottom-up, and therefore currently betray a strong hardware design ethos, and a correspondingly weak high-level software design model. Our current research (also funded by EPSRC) is investigating how to extend the PPF design methodology to address this rapidly developing embedded applications market using a software component-based approach, which we believe can provide a valuable method of unifying current disparate lowlevel hardware-software co-design models. Such solutions will surely become essential as complex multimedia embedded applications become widespread in consumer, commercial and industrial markets over the next decade. ANDY DOWNTON Colchester,
Oct.
2000
Acknowledgments
Although this book has only two named authors, many others have contributed to its content, both by carrying out experimental work and by collaborating in writing the journal and conference papers from which the book is derived. Early work on real-time handwritten addressrecognition, which highlighted the problem to be addressed, was funded by the British Post Office, supported by Roger Powell, Robin Birch and Duncan Chapman. Algorithmic developments were carried out by Ehsan Kabir and Hendrawan, and initial investigations of parallel implementations were made by Robert Tregidgo and Aysegul Cuhadar, all of whom received doctorates for their work. In an effort to generalise the ideas thrown up by Robert’s work in particular, further industrial contract work in a different field, image coding, was carried out, funded by BT Laboratories through the support of Mike Whybray. Many people at BT contributed to this work through the provision of H.261 image coding software, and (later) other application codes for speech recognition and microphone beam forming. Other software applications, including those for model-based coding, H.263, and Eigenfaces were also investigated in collaboration with BT. In addition to Mike Whybray, many others at BT laboratories provided valuable support for work there, including Pat Mulroy, Mike Nilsson, Bill Welsh, Mark Shackleton, John Talintyre, Simon Ringland and Alwyn Lewis. BT also donated equipment, including a Meiko CS2 and Texas TMS320C40 DSP systems to support our activities.
IX
X
As a result of these early studies, funding was obtained from the EPSRC (the UK Engineering and Physical Sciences Research Council) to investigate the emergent PPF design methodology under a directed program on Portable Software Tools for Parallel Architectures (PSTPA). This project - PSTESPA (Parallel Software Tools for Embedded Signal Processing Applications) - enabled us not only to generalise the earlier work, but also to start investigating and prototyping software tools to support the PPF design process. Chris Wadsworth from Rutherford Appleton Laboratories was the technical coordinator of this program, and has our heartfelt thanks for the support and guidance he provided over a period of nearly four years. Adrian Clark, with extensive previous experience of parallel image processing libraries, acted as a consultant on the PSTESPA project, and Martin Fleury was appointed as our first research fellow, distinguishing himself so much that before the end of the project he had been appointed to the Department’s academic staff. Several other research fellows also worked alongside Martin during the project: Herkole Sava, Nilufer Sarvan, Richard Durrant and Graeme Sweeney, and all contributed considerably to its successful outcome, as is evidenced by their co-authorship of many of the publications which were generated. Publication of this book is possible not only because of the contributions of the many collaborators listed above, but also through the kind permission of the publishers of our journal papers, who have permitted us to revise our original publications to present a complete and coherent picture of our work here. We particularly wish to acknowledge the following sources of tables, figures and text extracts which are reproduced from previous publications: The Institution of Electrical Engineers (IEE), for permission to reprint: l
portions of A. C. D ownton, R. W. S. Tregidgo, and A. Cuhadar, Topdown Structured parallelization of embedded image processing applications. IEE Proceedings Part I (Vision, Image, and Signal Processing), 141(6):438-445, 1994 as text in Chapter 1, as Figure 1.1 and A.l-A.4, and as Table A.1;
l
portions of M. Fl eury, A. C. Downton, schems for data farming, IEE Proceedings ital Techniques), in press at the time of as Figures 6.1-6.9, and as Tables 6.1 and
l
portions of A. C. D ownton, Generalised approach to parallelising image sequence coding algorithms, IEE Proceedings I (Vision, Image, and Signal Processing), 141(6):438-445, 1994 as text in Section 8.1, as Figures A.6-8.12, and as Tables 8.1 and 8.2;
l
portions of H. P. Sava, M. Fleury, Parallel pipeline implementation of Part I (Vision, Image, and Signal text in Section 9.2, and as Figures
and A. F. Clark, Scheduling Part E (Computers and Diqwriting, as text in Chapter 6, 6.2;
A. C. Downton, and A. F. Clark, wavelet transforms, IEE Proceedings Processing), 144(6):355-359, 1997 as 9.6-9.10;
xi
portions of M. Fleury, A. C. Downton, and A. F. Clark, Scheduling schemes for data farming, IEE Proceedings Part E (Computers and Digital Techniques), 146(5):227-234, 1994 as text in Section 11.9, as Figures 11.11-11.17, and as Table 11.6; portions of M. Fleury, H. Sava, A. C. Downton, and A. F. Clark, Design of a clock synchronization sub-system for parallel embedded systems, IEE Proceeclings Part E (Computers and Digital Techniques), 144(2):65-73, 1997 as text in Chapter 12, as Figures 12.1-12.4, and as Tables 12.land 12.2. Elsewier Science, for inclusion of the following: portions reprinted from Microprocessors and Microsystems, 21, A. Cuhadar, A. C. Downton, and M. Fleury, A structured parallel design for embedded vision systems: A case study, 131-141, Copyright 1997, with permission from Elsevier Science, as text in Chapter 3, as Figures 3.1-3.10, and as Table 3.1 and 3.2; portions reprinted from Image and Vision Computing, M. Fleury, A. F. Clark, and A. C. Downton, Prototyping optical-flow algorithms on a parallel machine, in press at the time of writing, Copyright 2000, with permission from Elsevier Science, as text in Section 8.4, as Figures 8.198.28, and as Tables 8.8-8.12; portions of Signal Processing: Image Communications, 7, A. C. Downton, Speed-up trend analysis for H.261 and model-based image coding algorithms using a parallel-pipeline model, 489-502, Copyright 1995, with permission from Elsevier Science, as text in Section 10.2, Figures 10.510.7, and Table 10.2. 3pringer Verlag, for permission to reprint: l
portions of H. P. Sava, M. Fleury, A. C. Donwton, and A. F. Clark, A case study in pipeline processor farming: Parallelising the H.263 encoder, in UK Paralle1’96, 196-205, 1996, as text in Section 8.2, as Figures 8.13-8.15, and as Tables 8.3-8.5;
l
portions of M. Fl eury, A. C. Downton, and A. F. Clark, Pipelined parallelization of face recognition, Machine Vision Applications, in press at the time of writing, as text in Section 8.3, Figures 5.1 and 5.2, Figures 8.16-8.18, and Tables 8.6 and 8.7;
a portions of M. Fl eury, A. C. Downton, and A. F. Clark, Karhunen-Loeve transform: An exercise in simple image-processing parallel pipelines, in Euro-Par’97, 815-819, 1997, as text in Section 9.1, Figures 9.4-9.5; l
portions of M. Fl eury, A. C. Downton, and A. F. Clark, Parallel structure in an integrated speech-recognition network, in Euro-Par’99, 9951004, 1999, as text in Section 10.1, Figures 10.1-10.4, and Table 10.1.
Academic l
Press, for permission
portions of A. C u h a d ar, D. G. Sampson, and A. C. Downton, A scalable parallel approach to vector quantization, Real- Time Imaging, 2:241-247, 1995, as text in Section 9.3, Figures 9.11-9.19, and Table 9.2.
The Institute to reprint: l
of Electrical
and Electronic
Engineers
(IEEE),
for permission
portions of M. Fl eury, A. C. Downton, and A. F. Clark, performance metrics for embedded parallel pipelines, IEEE Transactions in Parallel and Distributed Systems, in press at the time of writing, as text in Chapter 11, Figures 2.2-2.4, Figures 11.1-11.10, and as and Tables ll.l11.5.
John Wiley & Sons Limited, l
to reprint:
for inclusion
of:
portions of Constructing generic data-farm templates, M. Fleury, A. C. Downton, and A. F. Clark, Concurrency: Practice and Experience, 11(9):1-20, 1999, @John Wiley & Sons Limited, reproduced with permission, as text in Chapter 7 and Figures 7.1-7.7.
The typescript and WinEdt.
of this book was typeset by the authors
using I$‘,
MikTex
A. C. D. and M. F.
Contents
Foreword vii
Preface
ix
Acknowledgments
xix
Acronyms
Part I
Introduction
and Basic Concepts
1 Introduction 1.1 Overview 1.2 Origins 1.3 Amdahl’s Law and Structured Parallel Design to PPF Systems 1.4 Introduction 1.5 Conclusions Appendix A.1 Simple Design Example: The H.261 Decoder 2
Basic Concepts 2.1 Pipelined Processing
1 1 2
4 4 8 10 10 17 20 ... X/i/
xiv
CONTENTS
2.2
2.3 2.4 2.5 A.1 3
4
Pipeline Types 2.2.1 Asynchronous PPF 2.2.2 Synchronous PPF Data Farming and Demand based Scheduling Data-farm Performance Criteria Conclusion Appendix Short case studies
PPF in Practice 3.1 Application Overview 3.1.1 Implementation issues 3.2 Parallelixation of the Postcode Recognixer 3.2.1 Partitioning the postcode recognixer 3.2.2 Scaling the postcode recognixer 3.2.3 Performance achieved 3.3 Parallelixation of the address verifier 3.3.1 Partitioning the address verifier 3.3.2 Scaling the address veri’er 3.3.3 Address verification farms 3.3.4 Overall performance achieved 3.4 Meeting the Specification 3.5 Conclusion Appendix A. 1 Other Parallel Postcode Recognition Systems
5
25 26 27 28 30 31 31 37 38 39 39
40 41 43 47 47 49 50 50 51 53 53 53 57 58 59 60 62
Development of PPF Applications 4.1 Analysis Tools 4.2 Tool Characteristics 4.3 Development Cycle 4.4 Conclusion
Part II Analysis and Partitioning Sequential Applications
24
of
Initial Development of an Application 5.1 Confidence Building 5.2 Automatic and Semi-automatic
Parallelixation
67 67 69
CONTENTS
5.3 5.4 5.5 5.6 5.7 5.8 5.9 6
7
Graphical Simulation and Performance Analysis of PPFs 6.~ Simulating Asynchronous Pipelines 6.2 Simulation Implementation 6.3 Graphical Representation 6.4 Display Features 6.5 Cross-architectural Comparison 6.6 Conclusion Template-based Implementation 7.1 Template Design Principles 7.2 Implementation Choices 7.3 Parallel Logic Implementation 7.4 Target Machine Implementation 7.4.1 Common implementation issues 75 ‘NO WJ Implementation for Logic Debugging 716 Target Machine Implementations for Performance Tuning 7.7 Patterns and Templates 7.8 Conclusion
Part III 8
Language Proliferation Size of Applications Semi-automatic Partitioning Porting Code Checking a Decomposition Optimizing Compilers Conclusion
xv
71 72 73 75 77 77 79
81 82 82
84 88 89 93 95 96 99 100 101 102
104 109 112 113
Case Studies
Application Examples 8.1 Case Study 1: H.261 Encoder 8.1.1 Purpose of parallelixation 8.1.2 ‘Per macro block ’ quantixation without motion estimation 8.1.3 ‘Per picture ’ quantixation without motion estimation
117 118 119 119 123
xvi
CONTENTS
8.1.4
8.2
8.3
8.4
8.5 9
Design
9.1
9.2
‘Per picture’ quantization with motion estimation 8.1.5 Implementation of the parallel encoders 8.1.6 H.261 encoders without motion estimation 8.17 H.261 encoder with motion estimation 8.1.8 Edge data exchange Case Study 2: H263 Encoder/Decoder 8.2.1 Static analysis of H.263 algorithm 8.2.2 Results from parallelking H.263 Case Study 3: ‘Eigenfaces’ - Face Detection 8.3.1 Background 8.3.2 Eigenfaces algorithm 8.3.3 Parallelixation steps 8.3.4 Introduction of second and third famns Case Study 4: Optical Flow 8.4.1 Optical flow 8.4.2 Existing sequential implementation 8.4.3 Gradient-based routine 8.4.4 Multi-resolution routine 8.4.5 Phase-based routine 8.4.6 LK results 8.4.7 Other methods 8.4.8 Evaluation Conclusion Studies Case Study 1: Karhunen-Loeve Transform 0 91.1 Applications of the KLT 9.1.2 Features of the KLT 9.1.3 Parallelixation of the KLT 9.1.4 PPF parallelixation 9S.5 Implementation Case Study 2: 2D- Wavelet iPransform 9.2.1 Wavelet Transform 9.2.2 Computational algorithms 9.23 Parallel implementation of Discrete Wavelet Transform (D WT)
125
126 128
129 131 132 134 135 139 139
140 141 143 145 145 147 147 150 154 156 158 160 161 163
164 164 165 165 168 171 171 172 173 173
CONTENTS
9.2.4
9.3
9.4
Parallel implementation of oversampled WT Case Study 3: Vector Quantixation 9.3.1 Parallelixation of VQ 9.3.2 PPF schemes for VQ 9.3.3 VQ implementation Conclusion
xvii
10 Counter Examples 10.1 Case Study 1: Large Vocabulary ContinuousSpeech Recognition 10.1.1 Background 10.1.2 Static analysis of the LVCR system 10.1.3 Parallel design 10.1.4 Implementation on an SMP 10.2 Case Study 2: Model-based Coding 10.2.1 Parallelixation of the model-based coder 10.2.2 Analysis of results 10.3 Case Study 3: Microphone Beam Array 10.3.1 GrifithsJim beam-former 10.3.2 Sequential implementation 10.3.3 Parallel implementation of the G-J Algorithm 10.4 Conclusion
Part
IV
Underlying
Theory
176 179 180 181 183 186 189 190 190 191 193 195 196 196 198 202 202 203
204 206
and Analysis
of PPFs 11 Performance 11.1 Naming Conventions 11.2 Performance Metrics 11.2.1 Order statistics 11.2.2 Asymptotic distribution 11.2.3 Characteristic maximum 11.2.4 Sample estimate 11.3 Gathering Performance Data 11.4 Performance Prediction Equations 11.5 Results 11.5.1 Prediction results
211 212 212 213 216 217 219 220 221 223
224
... XV///
CONTENTS
11.6 Simulation Results 11.7 Asynchronous Pipeline Estimate 11.8 Ordering Constraints 11.9 Task Scheduling 11.9.1 Uniform task size 11.9.2 Decreasing task size 11.9.3 Heuristic scheduling schemes 11.9.4 Validity of Factoring 11.10 Scheduling Results 11.10.1 Timings 11.10.2Simulation results 11.11 Conclusion Appendix A.1 Outline derivation of Kruskal- Weiss prediction equation A.2 Factoring regime derivation 12 Instrumentation of Templates 12.1 Global Time 12.2 Processor Model 12.3 Local Clock Requirements 12.4 Steady-state Behavior 12.5 Establishing a Refresh Interval 12.6 Local Clock Adjustment 12.7 Implementation on the Paramid 12.8 Conclusion
Part V
225 227 230 235 236 236 237 238 238 238
240 241 242 242 243 247
248 249 249 250 253 256 257 259
Future Trends
13 Future Trends 13.1 Designing for Diflering Embedded Hardware 13.2 Adapting to Mobile Networked Computation 13.3 Conclusion
263 265 265 267
References
269
Index
299
Acronyms
AGP
Advanced
Graphics
Protocol
API
Application
APTT
Analysis,
AR
Autoregressive
ASIC
Application
ATR
Automatic
AWT
Abstract
Window
BSD
Berkeley
Standard
BSP
Bulk Synchronous
CCITT cdf
International Consultative Committee Telegraph Cumulative Distribution Function
CDT
Categorical
CIF
Common
COTS
Commercial
CPU
Central
CSP
Communicating
css
Central
Programming Prediction,
Interface
Template
Specific Integrated
Toolkit Circuits
Target Recognition Toolkit Distribution Parallel for Telephone and
Data Type Intermediate
Format
Off-The-Shelf
Processing
Unit
Sequential Processes
Synchronization
Server xix
Acronyms
CWT
Continuous
DAG
Directed
DCOM
Distributed
DCT
Discrete
DSP
Digital
Signal Processor
DVD
Digital
Versatile Disc
DWT
Discrete
FDDI
Fibre Distributed
FFT
Fast Fourier Transform
FIFO
First-In-First-Out
FIR
Finite Impulse Response
FPGA
Field Programmable
G-J
Griffiths-Jim
HMM
Hidden Markov
HP
Hewlett-Packard
HPF
High Performance
I/O IBM
Input/Output
IFFT
Inverse Fast Fourier Transform
IFR
Increasing
IS0
International
Standards
ITU
International
Telecommunications
JIT
Just-in-Time
JPEG
Joint Photographic
KLT
Karhunen-Loeve
LAN
Local Area Network
LVCR
Large Vocabulary
LWP
Light- Weight Process
MAC
Multiply
ME
Motion
MIMD
Multiple
MIT
Massachusetts
MMX
Multimedia
MPEG
Motion
Wavelet Transform Acyclic
Graph
Component
Object Model
Cosine Transform
Wavelet Transform
International
Data Interface
Gate Arrays
Model Fortran
Business
Machines
Failure Rate Organization
Experts
Union
Group
Transform Continuous-Speech
Accumulate
Recognition
Operation
Estimation Instruction
Multiple
Institute
of Technology
Extension
Picture
Experts
Data Streams
Group
Acronyms
MPI
Message-Passing
Interface
NOW
Network
NP
Non-polynomial
NT
New Technology
NUMA
Non-Uniform
OCR
Optical
Character
OF
Optical
Flow
ooc
Object-oriented
PC
Personal
Computer
PCA
Principal
Components
Pdf PE
Probability Processing
PK
Pollaczek-Khintchine
POSIX
Portable
Operating
PPF
Pipelined
Processor
Farms
PSNR
Peak Signal-to-Noise
Ratio
PSTN
Public System Telephone Network
PVM
Parallel Virtual
RISC
Reduced Instruction
RMI
Remote Method Invocation
RPC
Remote Procedure
RTE
Run-time
Executive
RTOS
Real-time
Operating
SAR
Synthetic
Aperture
SCSI
Small Computer
SIMD
Single Instruction
SMP
Symmetric
SNN
Semantic Neural Network
SPG
Series Parallel Graph
SSD
Sum-of-Squared-Differences
sss
Safe Self-Scheduling
STFT
Short-Time
TM
Trademark
UTC
Universal
of Workstations
Memory
Access
Recognition Coding Algorithm
Distribution
Function
Element System-IX
Machine Set Computer Call System Radar System Interface Multiple
Data Streams
Multiprocessor
Fourier Transform Time Coordinated
Xxii
Acronym
vcs
Virtual Channel System
VLC
Variable Length Encoder
VLIW
Very-Large Instruction Word
VLSI
Very-Large Scale Integration
VQ w.r.t.
Vector Quantization
ws
Wavelet Series
www
World Wide Web
with respect to
Part I
Introduction
and Basic Concepts
Introduction
1.1 OVERVIEW Much of the success of computers can be attributed to their generality, which allows different problems to be compiled and executed in different languages on the same or different processors. Parallel processing currently does not possess the generality of sequential processing’ because new degrees of freedom, such as the programming paradigm, topology (the connection pattern between processors [170, 199]), and number of processors, have been introduced into the design process. It appears that the potential offered by these additional design choices has led to an insistence by designers on obtaining maximum performance, with a consequent loss of generality. This is not surprising, because parallel solutions are typically investigated for the very reason that conventional sequential systems do not provide sufficient performance, but it ignores the benefits of generality which are accepted by sequential programmers. The sequential programming paradigm, or rather the abstract model of a computer on which it rests, was introduced by von Neumann [45] and has persisted ever since despite the evident internal parallelism in most microprocessor designs (pipelined, vector, and superscalar [115]) and the obvious bottleneck if there is just one memory-access path from the central processing unit (CPU) for data
‘Strictly >the term serial processing is more appropriate, as processing takes place on a serial machine or processor. The term sequential processing implies that the algorithms being processed are inherently sequential, whereas in fact they may contain parallel components. However, this book retains common usage and takes sequential processing to be synonymous with serial processing.
2
INTRODUCTlON
and instructions alike. The model suits the way many programmers envisage the execution of their programs (a single step at a time), perhaps because errors are easier to find than when there is an interleaving of program order as in parallel or concurrent programming paradigms.2 The Pipelined Processor Farms (PPF) design model, the subject of this book, can be applied in its simplest form to any Multiple Instruction Multiple Data streams (MIMD) [114] multiprocessor system.3 Single Instruction Multiple Data streams (SIMD) computer architecture, though current at the very-large scale integration (VLSI) chip-level, and to a lesser extent in multimedia-extension (MMX) microprocessor instructions for graphics support at the processor level [212], is largely defunct at the processor level, with a few honorable exceptions such as Cambridge Memory System’s DAP and the MasPar series of machines [13].4 Of the two categories of MIMD machines, the primary concentration is upon distributed-memory machines, where the address space is partitioned logically and physically between processors. However, it is equally possible to logically partition shared-memory machines, where there is a global address space. The boundaries between distributed and shared-memory machines have dissolved in recent times [70], a point to be returned to in Chapter 13.
1.2
ORIGINS
The origins of the PPF design method arose in the late 1980s as a result of research carried out at the University of Essex to design and implement a real-time postcode/address recognition system for the British Post Office (see Chapter 3 for a description of the outcome of this process). Initial investigation of the image analysis and pattern recognition problems demonstrated that significant research and development was needed before any kind of working demonstrator could be produced, and that, of necessity, the first demonstrator would need to be a non-real-time software simulation running on a workstation. This provided the flexibility to enable easy experimental evaluation and algorithm updates using offline databases of address images,
2Shared-memory machines can also relax read-write access across the processor set ranging from strong to weak consistency, presenting a continuum of programming paradigms [259]. 3Categorization of processors by the multiplicity of parallel data and instruction streams supported is a well-known extension of von Neumann’s model [65]. 4Systolic arrays are also used for fine-grained, signal processing [200] though largely again at the VLSI level. In systolic designs, data are pumped synchronously across an array of processing elements (PEs). At each step a different stage in processing takes place. Wavefront processors are an asynchronous version of the systolic architecture. Other forms of instruction level parallelism are very-large instruction word (VLIW) DSPs (digital signal processors) and its variant explicitly parallel instruction computing (EPIC) [319]. The idea of transferring SIMD arrays such as the DAP to VLSI has also been mooted. The DIP ‘chip [66] is an experimental and novel SIMD VLSI array.
ORIGINS
3
and also a starting point for consideration of real-time implementation issues. In short, solving the problem at all was very difficult; generating a real-time solution (requiring a throughput of 10 envelope images/second, with a latency of no more than 8 seconds for processing each image) introduced an additional dimension of processing speed which was beyond the bounds of available workstations. A literature survey of the field of parallel processing at that time showed that numerous papers had been published on parallelization of individual image processing, image coding and image analysis algorithms (see, e.g. , [362]), many inspired by the successof the transputer [136]. Most of these papers were of limited generality however, since they reported bespoke parallelization of specific well-known algorithms such as 2-D filters, FFTs, DCTs, edge detectors, component labeling, Hough transforms, wavelets, segmentation algorithms, etc. Significantly, examination of many of these customized parallel algorithms revealed, in essence,the same solution; that of the single, demandbased, data farm. Practical image analysis and pattern recognition applications, however, typically contain a number of algorithms implemented together as a complete system. Like the postal address reading application, the CCITT H.261 encoder/decoder algorithm [49] is also a good illustration of this characteristic, since it includes algorithms for discrete cosine transformation (DCT), motion estimation and compensation, various filters, quantizers, variable length coding, and inverse versions of several of these algorithms. Very few papers addressed the issue of parallelizing complete systems, in which individual algorithm parallelization could be exploited as components. Therefore, a clue to an appropriate generic parallel architecture for embedded applications was to view the demand-based processor farm as a component within a higher-level system framework. From our point of view, parallel processing was also simply a means to an end, rather than an end in itself. Our interest was in developing a general system design method for MIMD parallel processors, which could be applied after or during the initial iterative algorithm development phase. Too great a focus on performance at the expense of generality would inevitably have resulted in both implementations and design skills that rapidly became obsolete. We therefore aimed to support the early, architecture independent stages of the design process, where parallelization of complete image processing applications is considered, by a process analogous to stepwise refinement in sequential program design [312, 3351. Among the advantages of the PPF design methodology which resulted are the following: l
Upper bound (idealized) throughput scaling of the application is easily defined, and aspects of the application which limit scaling are identified.
l
Input/output
latency is also defined and can be controlled.
4
1.3
1NTt?ODUCT/ON
l
Performance is incrementally scalable up to the upper bound (i.e. there are no quantization restrictions on the number of processors which can be used), so that real-time performance requirements can be met exactly.
l
The granularity of parallelism is maximized, thus minimizing the design effort required to move from the sequential to the parallel implementation.
l
Design effort i s focused on each performance stage in turn, by identifying the throughput
AMDAHL’S
LAW AND
STRUCTURED
9
bottleneck of each pipeline latency, and scalability.
PARALLEL
DESIGN
Amdahl’s law [15, 161 is the Ohm’s law of parallel computing. It predicts an upper bound to the performance of systems which contain both parallelization and inherently sequential components. Amdahl’s law states that the scaling performance of a parallel algorithm is limited by the number of inherently sequential operations in that algorithm. Consider a problem where a fraction f of the work must be performed sequentially. The speed-up, S, possible from a machine with N processors is:
If f = 0.2 for example (i.e 20% of the algorithm is inherently sequential), then the maximum speedup however many processors are added is 5. As will be shown in later chapters, applying Amdahl’s law to multi-algorithm embedded systems demonstrates that the scaling which can be achieved is largely defined, not by the number of processors used, but by any residual sequential elements within the complete application algorithm. Thus effective system parallelization requires a method of minimizing the impact of residual sequential code, as well as of parallelizing the bulk of the application algorithm. In the PPF design methodology, pipelining is used to overlap residual sequential code execution with other forms of parallelism.
1.4
INTRODUCTION
TO PPF SYSTEMS
A PPF is a software pipeline intended for recent, accessible, parallel machines. Examples of such lowly parallel machines [278], which now abound, are networks of workstations (NOW), processor farms, symmetric multiprocessors A feature of such ma(SMP) and small-scale message-passing machines. chines is that scalability is localized [93] and consequently the communication diameter is also restricted. The commercial off-the-shelf (COTS) processors used within such machines will outstrip the available interconnect bandwidth
INTRODUCTlON
5
TO PPF SYSTEMS
if combined in large configurations since such processors were not designed with modularity in mind. To avoid this problem in PPF, a pipeline is partitioned into a number of stages, each one of which may be parallel. PPF is primarily aimed at continuous-flow systems in the field of signal processing, image-processing, and multimedia in general. A continuous-flow system is one in which data never ceaseto arrive, for example a radar processor which must always monitor air traffic. These systems frequently need to meet a variety of throughput, latency, and output-ordering specifications. It becomes necessary to be able to predict performance, and to provide a structure which permits performance scaling, by incremental addition of processors and/or transfer to higher performance hardware once the initial design is complete. The hard facts of achievable performance in a parallel system are further discussedin Section 2.4. There are two basic or elementary types of pipeline components: asynchronous and synchronous, though many pipelined systems will contain some segments of each type. PPF caters for any type of pipeline, whether synchronous, asynchronous or mixed; their performance characteristics are discussed in detail in Section 2.2. Pipeline systems are a natural choice for some synchronous applications. For example, a systolic pipeline-partitioning methodology exists for signal-processing algorithms with a regular pattern [237]. Alternatively, [8] notice that there is an asynchronous pipeline structure to the mind’s method of processing visual input which also maps onto computer hardware. If all information flow is in the forward direction [8] then the partitions of the pipeline mirror the peripheral, attentive, and cognitive stages of human vision [232]. The CMU Warp [18], the Cytocomputer [341], PETAL and VAP [56] are early examples of machines used in pipelined fashion for image processing.5 Input to the pipeline either takes the form of a succession of images grouped into a batch (medical slides, satellite images, video frames and the like) or raster-scan in which a stream of pixels is input in the same order as a video camera scans a scene that is in horizontal, zigzag fashion. PPF generalizes the pipeline away from bespoke hardware and away to some extent from regular problems. Examples of applicable irregular, continuous-flow systems can be found in vision [50] (seeChapter 3), radar [97], speech-recognition processing [1331, and data compression [52]. Chapters 8 and 9 give further detailed casestudies where PPF has been consciously applied. PPF is very much a systems approach to design, that is, it considers the entire system before the individual components. Another way of saying this is that PPF is a top-down as opposed to a bottom-up design methodology. For some years it has been noted [214] that many reported algorithm examples merely form a sub-system of a vision-processing system while it is a complete
5The using
common a linear
idea across these systolic array.
machines
is to avoid
the expense
of a 2D systolic
array
by
6
INTRODUCTION
system that forms a pipeline. Various systems approaches to pipeline implementation are then possible. With a problem-driven approach it may be difficult to assessthe advantages and disadvantages of alternative architectures for &sign any one stage of a problem. However, equally an architecture-driven ties a system down to a restricted range of computer hardware. In PPF, the intention is to design a software structure that, when suitably parameterized, can map onto a variety of machines. Looking aside to a different field, Oracle has ported its relational database system to a number of apparently dissimilar parallel computers [337] including the Sequent Symmetry shared-memory machine and the nCube2 MIMD message-passingcomputer. Analogously to the database abstract machine, the software pipeline is a flexible structure for the PPF problem domain. Having settled on a software pipeline, there are various forms of exploitable parallelism to be considered. The most obvious form of parallelism is temporal multiplexing, whereby several complete tasks are processedsimultaneously, without decomposing individual tasks. However, simply increasing the degree of temporal multiplexing, though it can improve the mean throughput, does not change the latency experienced by an individual task. To reduce pipeline traversal latency, each task must be decomposedto allow the component parts to experience their latency . in parallel. Geometric parallelism (decomp by some partition of the data) or algorithmic parallelism (decomposition by function) are the two main possibilities available for irregularly structured code on medium-grained processors.6 After geometric decomposition, data must be multiplexed by a farmer process across the processor farm which is why in PPF data parallelism is alternatively termed geometric multiplexing. When a processor farm utilizes geometric multiplexing, it is called a data farm, and certainly the term data farm is more common in the literature.7 This book does not include many examples of algorithmic parallelism, not by intent but because the practical opportunities of exploiting this form of parallelism are limited. An early analysis [277] in the field of single-algorithm image processing established both the difficulty of finding suitable algorithmic decompositions and the limited speed-up achievable by functional decomposition. However, algorithmic parallelism does have a role in certain applications, which is why it is not discounted in PPF. For example, pattern matching may employ a parallel search [202], a form of OR-parallelism, whereby alternative searchestake place though only the result of successfulsearchesare retained?
6Dataflow computers [340] have been proposed as a way of exploiting the parallelism inherent in irregularly structured code (Le. code in which there are many decision points resulting in branching), but though there are research processors [79], no commercial dataflow computer has ever been produced. 7The term data parallelism is an alternative to geometric parallelism, but this term has the difficulty that data parallelism is associated with parallel decomposition of regular code (i.e. code with few branch points) by a parallel compiler. 8Divide-and-conquer search algorithms may be termed AND-parallelism, as the result of parallel searches may be combined through an AND-tree [294].
INTRODUCTION
TO PPF SYSTEMS
7
Bringing together the preceding discussion, it can be stated that: 1. A data set can be subdivided over multiple processors (data parallelism or geometric multiplexing). 2. The algorithm can be partitioned over multiple processors (algorithmic parallelism). 3. Multiple processorscan each process one complete task in parallel (processor farming or temporal multiplexing). 4. The algorithm can be partitioned serially over multiple processors (pipelining) (pipelining being an instance of algorithmic parallelism). 5. The four basic approaches outlined above can be combined as appropriate. The field of low-level image processing [74] illustrates how these forms of parallelism can be applied within a processor farm: Geometric multiplexing An example of geometric multiplexing is where a frame of image data is decomposed onto a grid of processors. Typical low-level image-processing operations such as convolution and filtering can then be carried out independently on each sub-image requiring reference only to the four nearest neighbor processorsfor boundary information. To adapt such operations to a processor farm, the required boundary information for each processor can be included in the original data packet sent to the processor. Algorithmic parallelism In the case of algorithmic parallelism, different parts of an algorithm which are capable of concurrent execution can be farmed to different processors, for example the two convolutions with horizontal and vertical masks could be executed on separate processors concurrently in the case of a Sobel edge detector [290, 751. The advantage of a processor farm in this context is that no explicit synchronization of processors is required; however, the algorithm itself normally defines explicitly the possible degree of parallelism (i.e. incremental scaling is not possible). Temporal multiplexing Applying each of a sequence of images to a separate processor does not speed up the time to process an individual image, but enables the average system throughput to be scaled up in direct proportion to the number of processors used. The approach is limited by the allowable latency between the input and output of the system, which is not reduced by temporal parallelism. Pipelining Pure pipelining has the same effect as temporal multiplexing in speeding up overall application throughput without reducing the latency
8
INTRODUCTlON
for any particular image, but is achieved by sequentially subdividing the complete application algorithm and placing each component onto a separate processor. The throughput increase is constrained by the maximum processing time for any one stage within the pipeline. Thus, the pipeline of four processors shown in Fig. l.la increases the steady-state task throughput from 0.1 tasks/second for a single sequential processor to 0.25 tasks/second (limited by the slowest pipeline stage), a speedup of 2.5. Note however that the latency (delay between task input and task output) increases from 10 seconds for the sequential algorithm to 15 seconds (3 x 4 seconds + 3 seconds for the final stage) for the unbalanced pipeline shown in Fig. l.la). The role of pipelining within the PPF design philosophy is to increase throughput and reduce latency by allowing necessarily independent components of an application (some of which may be inherently sequential) to be overlapped. By combining the techniques described above, and mapping a PPF architecture onto the pipeline of stages which comprises any embedded application, both the throughput and the latency of the application can be scaled. Fig. l.lb illustrates the effect of using temporal multiplexing alone to achieve throughput scaling: when the throughput of each pipeline stage is matched at 1 task/second, a speedup of 10 is achieved with the same latency as the original sequential algorithm. Of course, exactly the same throughput scaling (with unchanged latency) could be achieved using a single processor farm, with each processor executing a copy of the complete application. The reason for using a pipeline instead is to break down the overall application into its sub-components, so that data or algorithmic parallelism can be exploited to reduce latency as well as increase throughput. Finally, Fig. 1.1~ illustrates the exploitation of data or algorithmic parallelism in each pipeline stage instead of temporal multiplexing: in this case, the same speedup of 10 is achieved, but with a reduction of latency to 4 seconds. Appendix A.1 below illustrates how basic profiling data, extracted from execution of a sequential image coding algorithm, can be used to guide the PPF design process to achieve a scalable parallel implementation of the algorithm with analytically defined performance bounds.
1.5
CONCLUSIONS
The primary requirement in parallelizing embedded applications is to meet a particular specification for throughput and latency. The Pipeline Processor Farm (PPF) design model maps conveniently onto the software structure of many continuous data flow embedded applications, provides incrementally scalable performance, and enables upper-bound scaling performance to be easily estimated from profiling data generated by the original sequential imple-
Per-stage
1s
1s
a) Simple pipeline Throughput = 0.25 jobs/s Latency = 15 s 2s 4s 3s
b) PPF with temporal parallelism Throughput = 1 job/s Latency = 10 s
Different data or algorithm on each processor farm worker.
c) PPF with data/algorithmic parallelism Throughput = 1 job/s Latency = 4 s Fig. 1.1
Idealized
examples of PPF.
10
INTRODUCTlON
mentation. Using the PPF model, sequential sub-components of the complete application are identified from which data or algorithmic parallelism can be easily extracted. Where neither of these forms of parallelism is exploitable ( i.e. the residual sequential components identified in Amdahl’s law), temporal multiplexing can often be used to match pipeline throughput without reducing latency. Each pipeline stage will then normally map directly onto the major functional blocks of the software implementation, written in any procedural language. Furthermore, the exact degree of parallelization of each block required to balance the pipeline can be determined directly from its sequential execution time.
Appendix A.1
SIMPLE
DESIGN
EXAMPLE:
THE
H.261
DECODER
Image sequence coding algorithms are well known to be computationally intensive, due in part to the massive continuous input/output required to process up to 25 or 30 image frames per second, and in part to the computational complexity of the underlying algorithms. In fact, it was noted (in 1992) [380] that it was only just possible to implement the full H.261 encoder algorithm for quarter-CIF (176 x 144 pixels) images in real time on DSP chips such as the TMS 32OC30. In this case study, a non-real-time H.261 decoder algo rithm developed for standards work at BT Laboratories and written in C, was parallelized to speedup execution on an MIMD transputer-based Meiko Computing Surface. Results presented are based upon execution times measured when the H.261 algorithm was run on sequencesof 352 x 288 pixel common intermediate format (CIF) images. Fig. A.1 shows a simplified representation of the H.261 decoder architecture. The decoder consists of a 3-stage pipeline of processes,with feedback of the previous picture applied around the second stage. Feedback within a pipeline is a key constraint on parallelism, since it restricts the degree to which temporal multiplexing can be exploited: in the H.261 decoder, the reconstructed previous frame is used to construct the current frame from the decoded difference picture. Table A.1 summarizes the most computationally intensive functions within the BT H.261 decoder, and is derived from statistics generated by the Sun profiling tool gprof [138] while running the decoder on 30 image frames of data on a Sparc2 processor. To simplify interpretation, processing times have been normalized for one frame of data. The 10 functions listed in the table constitute 99.2% of total execution time. Program execution of the H.261 decoder can be broken down on a per-frame basis into a pipeline of three major components: Tl
frame initialization
(functions 1 and 2 in Table A.l);
SlMPLE
1 iteration&me
+
DESIGN
EXAMPLE:
THE H.261
396 iterations&me T2 Functions
Tl Functions 192
1 iterationhame
I )t
3-8
T3 Functions
-)lc
9,lO
I
0.665s
11
DECODER
5.513s
0.925s
previous picture
Fig. A.1
Simplified
Table A.1
representation
Summary
Execution
of the H.261 decoder execution
Profile Statistics
Sequence
Function
name
1 2 3 4 5 6 7 8 9 10
clear-picture h26Ldecode-picture inverserunlevel-picture tminversescan-change-picture h261inverse-quantize-picture reconstruct lh261 inverse-transform-picture copymacro-block write-picturefile macro-block-toline
timing.
for the H.261 Decoder
Normalized
Execution 0.098 0.567 0.284 0.346 0.750 1.695 2.199 0.239 0.685 0.240
Time
(s)
12
INTRODUCTION
T2 frame decoder loop (functions 3-8 in Table A-1); and T3 frame output (functions 9 and 10 in Table A.1). The first and last of these components are executed once for each image frame, whereas the middle component contains considerable data parallelism and involves a loop executed 396 times (once for each 16 x 16 pixel macroblock making up a CIF picture). It is therefore clear that considerable scope exists for speeding up the middle stage of the pipeline by exploiting data parallelism. Temporal multiplexing cannot be utilized because each image frame is reconstructed by means of a difference picture added to the motion-compensated previous frame (although it would be possible to partially overlap the decoding of consecutive frames). Since pipeline stages Tl and T3 are inherently sequential, direct application of Amdahl’s law to the data in Fig. A.1 shows that f = 0.22, giving a maximum speedup of only 4.55. An asymptotic approach to this speedup could be obtained by parallelizing the decoder using a single processor farm, with the data-parallel component T2 farmed onto worker processors, and the remaining code executed on the master processor. The upper-bound predicted speedup for the PPF is presented graphically in Fig. A.2 and may be represented theoretically by the following piecewise approximation: (n-2) s
2 T; i= 1
-7-‘2
3
3
3
c
S
_ -
Z
i=l -ijpO2+%,
where the first and last stagesof the PPF contain a single processor, the second processor farm stage contains n - 2 processors, and TI-TS are execution times of the three stages of the pipeline shown in Fig. A.2. As the throughput for a PPF is defined solely by the slowest pipeline stage, its speedup is given by the ratio of sequential application execution time to the execution time for this stage alone (this illustrates the advantage of the pipeline in overlapping execution of residual sequential components). Where (as in this case) the slowest stage is perfectly parallelizable (i.e. it contains no residual sequential elements and thus f = 0 in Amdahl’s law), linear speedup is obtained up to the point where the scaled stage is no longer the slowest. The first equation defines this casewhere the performance is increasing linearly as the number of workers in the processor farm increases (S is proportional to n); this continues until the execution time for the processor farm drops below that of the next slowest stage, T3 in this case. The second equation then defines the fixed scaling achieved for any further increase in processor numbers (S is fixed and independent of n). It is assumed that the processor farm implementing the middle stage of the pipeline receives its work packets directly from the first stage and passes
SlMPLE
DES/GA/
EXAMPLE:
13
THE l-i.261 DECODER
0-
R
5 --
ti t3.t
4 -3 -2 -1 dP 01
1
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I I
I
2
3
4
5
6
7
8
9
10
11
12
13
14
Nuder
Fig. A.2
Idealized
ofprocessors
and actual speedup for the H.261 decoder.
its results directly to the third stage, as in the topology of Fig. A.3, where an implementation with five worker processors is shown. The analysis is of course idealized, ignores communication overheads, and assumesstatic task characteristics. As can be seen from Fig. A.2, the performance is predicted to scale linearly up to six workers (8 processorstotal).
\ 1
)2.
0 Tl
T2
Fig. A.3
PPF topology
for a 3-stage pipeline
with 5 workers in the second stage.
14
Actual scaling performance results are also presented in Fig. A.2, for two different practical cases. In both cases,the scaling performance is less than that predicted in the idealized graph, due to communication overheads being neglected, but the general shape of the graphs is in other respects as predicted. The maximum speedup obtained (5.59) exceeds the limit predicted by Amdahl’s law, thus demonstrating the advantage which the PPF has compared with a single processor farm implementation. In practice, transputer communication links do not provide sufficient bandwidth for real-time communication of H.261 CIF picture data structures, and therefore communication overheads substantially limit the performance scaling which can be achieved in a transputer-based system. On the AMD Share family of processorswith six link ports, real-time parallel processing of images sequencesis far more practicable. For example, the ADSP-21160 [14], running at 100 MHz, supports ‘glueless’ multiprocessing9 and floating point like the transputer, but now is superscalar, with a maximum of six issuesper cycle. In the first implementation, each image was simply subdivided into a number of horizontal strips defined by the number of processor farm workers, in line with the idealized model of data parallelism presented earlier. As can be seen from Fig. A.4(a), this results in a series of black strips in the reconstructed image, where data adjacent to each worker’s sub-image were not available for constructing the motion compensated previous image. In the second implementation, additional rows of macroblocks at the boundaries of the sub-image processed by each farm worker were exchanged in a second communication phase between the master and worker processors in the processor farm, after the difference image had been decoded. This enables the full motion compensated previous image to be reconstructed, as shown in Fig. A.4(b), but results in an additional communication overhead, which decreasesscaling performance compared with the case where edge data are not exchanged.
SIMPLE
DESIGN
EXAMPLE:
THE H.261
DECODER
Fig. A.4 Sample image output by the parallel H.261 decoder with 5 workers out edge data exchange and (b) with edge data exchange.
15
(a) with-
2 Basic Concept
-
S
PPF is primarily intended for embedded systems [313], which are not the traditional target for parallel processing, and, as will become apparent, are not well covered in the literature, where the emphasis is on general-purpose programming. Embedded systems are dedicated applications of computers running within some larger application framework or context. Most embedded systems are continually available, either processing data, or reacting to external events [35]. Increasingly, with the development of more complex computer applications and tighter deadlines, embedded systems cannot be designed without utilizing parallel processing. Consider automatic target recognition (ATR) of aircraft found by Synthetic Aperture Radar (SAR) reported in [343], Fig. 2.1. The design of this application, though developed independently of PPF, has many of the characteristic design features of a PPF. There is: a single flow of processing control through a pipeline; interest in accelerating the target identification stage by some form of processor farm (or other topology); and use of Commercial-off-theShelf (COTS) h ar d ware configured in parallel. The result is a cost-effective, scalable solution which will meet (presumably) latency and throughput targets. Ad .ditionally, rather like the two-level hardware employed in a number of the applications covered in later chapters of this book, a Myrinet high-speed network [103] is deployed independently of the processing nodes, which can be PowerPc RISC (reduced instruction set) microprocessors, AMD SHARC DSPs, or Lucent Orca FPGAs (field programmable gate arrays). There is also a need to coordinate the flow of data across the hierarchy of ATR algorithms, requiring a system-wide view. 17
18
BASIC
CONCEPTS
Having arrived at a design for (say) a DSP processor at the computation layer, why consider an FPGA alternative? Why, in fact, partition an application between a communication structure and computation layer? The key problem a parallel system designer must face is how to make a system scalable. This is not simply because larger (or smaller) problems can be tackled solely by adding hardware in an incremental fashion, without otherwise changing the design, important though a modular design remains. Equally important is that uniprocessor performance increases in proportion to the number of transistors on a microchip, which has been observed to double approximately every eighteen months (the well-known Moore’s law’). Therefore, a design tied to a specialized parallel machine may well be rapidly overtaken in terms of price and performance by a uniprocessor implementation. The principal reason for the shift to COTS hardware is to exploit the economies in scale that arise within the uniprocessor market, which lead to exponential gains in performance. In other words, by exchanging the computation hardware within the design, which can also be modular, a design is made doubly scalable, and hopefully future-proof. As the life cycle of a typical commercial microprocessor is less than five years, while the life time of many embedded products is much longer (e.g. an avionics system has a lifetime greater than thirty years), system (or code) portability [23] is an important method of amortizing the investment in the original embedded software. A PPF design is a pipeline of processor farms. The essenceof a processor farm within PPF is one central farmer, manager, or controller process, and a set of worker or slave processesspread acrossthe processor farm. Notice that there is no insistence in PPF on having a single worker process per processor, though in fact our farm template design (Chapter 7) does not exploit parallel slackness [329] by having more than one process to a processor. In a sharedmemory MIMD machine, worker threads [189] replace worker processes, a thread being a single line of instruction control existing in a shared or global address space. The role of the farmer is not simply to coordinate the activity of the workers but additionally to passpartially-processed work onto the next stage of processing. By introducing modularity, each module being a farm, it becomes possible to cope with heterogeneous hardware, and separately to scale each farm as larger problems or versions of the original problem are tackled. PPF is appropriate for all applications with continuous data input/output, a characteristic typical of soft, real-time, embedded systems.2 However, PPF is by no means a panacea for all such embedded systems, and in Chapter 10,
lMoore’s law % 1 named after Gordon Moore, co-founder and Chairman of Intel, who discovered the law in 1965. 2Soft real-time systems as opposed to hard, real-time systems are those in which responsivendss to deadlines can be relaxed. Hard, real-time systems [216] usually involve the control of machinery, such as in fly-by-wire avionics and industrial manufacturing control, and are not the subject of this book.
19
radar 1 scans I-
Synthetic Aperture Radar sensor
SAR
and pre-processing to form images
Focus of attention - location of regions of interest
FOA
--I-
_---
,-- _---
Second-level detection - template matching
SLD /
’ ’ ‘level 1 comms. processor: LANAI level 2 computation: DSP, RISC, \ ., FPGA \\ \\
reporting
J,targets Fig. 2. I Sandia National Laboratory’s the Myricom Parallel Stage.
Automatic
Target Recognition
System showing
some counter-examples encountered by the authors are considered. In fact, it may always be possible for a better, optimized solution to be found for any application. However, first consider how long the development task will take; whether the solution will transfer easily to alternative hardware; whether late algorithmic changes can easily be accommodated and so on. These are the problems of medium- and larger-scale systems which are expected to persist over more than one generation of hardware. To tackle such applications re-
20
BASIC
CONCEPTS
quires high-level, systems thinking, which, because of its generality, can be deceptively hard. Another way of seeing the processor farm is as a client-server system [378] where there is one client (the farmer) and multiple servers (the workers). Workers only interact with the farmer, usually directly, though a per-farm multicast has proved useful (see the H.263 example in Chapter 8) and has become a feature of our farm template design, Chapter 7. When demandbased scheduling of work takes place, unlike the classic client-server model, the workers request further work from the farmer. The ability of a server to make a request introduces a circular path of communication. However, deadlock is avoided becausethe farmer will normally only send work when it is requested. An introduction to the demand-based method of processor farming occurs in Section 2.3, and this form of scheduling is revisited in Chapter 11. Workers for the most part perform identical tasks. However, in our definition of the processorfarm, algorithmic parallelism can occur, whereby different functions of an algorithm are distributed among the worker processes. There are instances where divide-and-conquer is a way of distributing work to the farm [60]. In the divide-and-conquer paradigm, workers perform an identical algorithm but at varying levels of granularity, for example when decomposing an FFT (Fast Fourier Transform). However, in most cases, including the 2D Fast Fourier Transform (FFT) (a staple of many signal-processing algorithms), equal-sized tasks are easier to implement; are at least as efficient; and are portable.3
2.1
PIPELINED
PROCESSING
The role of pipelining within the PPF design method is to increase throughput and reduce latency by allowing necessarily independent components of an application (some of which may be inherently sequential) to be overlapped. The performance of a pipeline will depend on its organization which in turn is dependent on the application. The application may consist of multiple algorithms within which may exist varying types of parallelism. One common way to categorize algorithms is through granularity which is the ratio between communication and computation. In other words, granularity is the amount of computation that can take place before a result is exchanged between processors. Two considerations occur: is there sufficient granularity within the algorithm, and can the multiprocessor architecture exploit that granularity ? As was pointed out in Chapter 1, fine-grained algorithms with a regular structure are no longer catered for at the processor level. According to [121], most scientific and engineering applications lie in
us FFT 3Numero [240] are available,
algorithms su .itable for vector but are n ot portable.
processors
[348]
or VLSI
implementations
PlPELlNED
PROCESSHVG
21
the middle of the granularity spectrum, and in the middle of a code regularity spectrum and therefore it makes sense to design general-purpose parallel machines for that market. Broadly, on current PPF hardware medium- and coarse-grained parallelism is exploitable as befits the target hardware, that is the lowly parallel configurations that are current in embedded systems. How can work be organized across a pipeline? The following per-stage work allocation patterns can be distinguished (Fig. 2.2): data-flow is used when there is no need to load balance as there is a steady work arrival rate combined with an approximately constant per-task processing time. Local buffering of tasks can be employed to ease short-term blockages, but then a scheduling regime becomes necessary, e.g. [219]. Data-flow may be appropriate if there is no suitable decomposition of jobs (temporal multiplexing in PPF nomenclature), e.g. for the parallelization of wavelet transforms [317].
Macro-task
is used to give closer control of task scheduling particularly when processing time is data (content) dependent. Notice that the task processing time can include variable communication times, for point-topoint networks, and the effect of background processing. Load balancing can be automatic if returning processed work (or a token signifying task completion) forms the basis of a request for more work. A static scheduling phase (i.e. with no system feedback) will be necessary at load-up time. Presently only demand-based scheduling is used as it is a general solution which can be captured in a data-farm template. Where the parallel hardware is known, other methods of load-balancing may be appropriate though not necessarily superior, e.g. linear programming based on mean-value statistics has been successful for farms operating in a store-and-forward communication regime [338].
A data-farm
paths will exist particularly if an algorithm has been designed originally for a sequential machine. The H.261 and later H.263 hybrid video-stream encoder and decoder applications exhibit multiple feedback routes. The stage awaiting feedback is synchronous.
Feedback
pipelines may be a way of coping with feedback. For example, in Fig. 2.2 C, the time to complete stages one and three together may approximately balance the time to complete stage two. Therefore, the output from stage three is fed-back to stage one, Fig. 2.2 D. In the parallelization of H.261, the timings from profiling of the sequential code established the approximate equivalence between two stages and a folded-back pipeline was used.
Folded-back
Multiple
farms (Fig. 2.3) are suitable when independent algorithms can be grouped in the same pipeline stage, with an obvious reduction in the pipeline traversal time. It may also become easier to balance or scale other stages of the pipeline. The Karhunen-Loeve transform (KLT)
22
BASIC
CONCEPTS
parallelization, Chapter 9, is an example of a single algorithm where dual farms are possible. When differing communication patterns or job service rates are segregated there is a increase in performance due to the decrease in variance. This is a standard result from queueing theory, for instance consider the Pollaczek-Khintchine (P-K) formula for the expected queue length in M/G/l systems [187].4
farmer
1
farmer
2
2 e
Fig. 2.2 Pipeline work allocation: folded-back pipeline.
output
a) data-flow
farm; b) data-farm;
c) feed-back;
d)
is necessary either when the granularity of a stage is such that with the available hardware it is not sensible to parallelise, or a brief phase requiring global or irregular data dependencies exists. Otherwise, where regional data dependencies are present, data-flow and data-farming work allocation can be adapted by sending out bordering data, as is the casefor spatial filtering of images. A general-purpose processor topology which can accomplish global data exchange is the uni-directional ring since it can be embedded into many other topologies [336]. If centralization is necessary it is accomplished by a single processor or by a uni-ring stage. Alternative hardware may be employed to accelerate centralized stages. For example, histogram equalization of
Centralization
4The PK formula is E[n] = p + ,w, number in the queue, p is the availability, E[S2] in the numerator.
where E is the expectation operator, n is the and S is the service time. Notice the effect of
PlPELlNED
23
PROCESSING
an image which has two short-lived phasesfor moderately sized images separated by a global exchange of information can be accomplished by an FPGA linked to the address-bus of a host processor.
L---------------------------------------w \
I
I
I I
\
I I
farmer 2a
I
/ -----------------------w--v-------------
Fig. 2.3
Dud-farm
pipeline
stage.
In PPF systems, care should be taken that the farmer does not become an under-used resource, responsible only for scheduling. On machines, such as Meiko’s CM-5 or Transtech’s Paramid, a dual processor arrangement allows a farmer process to be placed on a communication coprocessor while a worker process resideson the computation processor [113]. On the Texas Instruments TMS320C80 [27], a control processor with accessto floating-point facilities supervises four support processors, all on the sameintegrated circuit. If farmers are directly connected in the design, a fast bus can link the processors, while point-to-point communication is used to form the worker network. A farm becomes the smallest replaceable unit in fault-tolerance terms [97]. Data-flow pipelines and dual pipelines do not have this flexibility.
24
BASK
2.2
PIPELINE
CONCEPTS
TYPES
Both fundamental types of pipeline, synchronous and asynchronous, are provided by PPF. A purely asynchronous pipeline is obviously one in which there are no synchronous stages. If a task can be decomposed then its individual parts can proceed independently along the pipeline and consequently be independently scheduled at each of the stages of the pipeline. If the task components, that is, processed data or composite results, only need to be reassembled at the output of the pipeline, the latency can be reduced considerably. In practice, a partial reassembly may take place at various stages within an asynchronous pipeline. The handwritten postcode recognition system in Chapter 3 is an asynchronous pipeline, but the characters of the postcodes still needed to be reassembled at the final stage. Furthermore, identified postcodes have to emerge from the pipeline in the same order that the original handwritten address was input (in order to be printed as a phosphorescent dot code on the correct envelope), an output ‘ordering’ constraint. The effect of an ordering constraint at the output can be limited if output buffering is provided because there are no further stages of the pipeline. However, it is perfectly possible for a variety of ordering constraints to occur. To estimate the performance of an asynchronous pipeline with such a constraint, it may be possible to consider the pipeline as if no such constraint existed and then superimpose the percentage degradation which will result from a constraint, Chapter 11. Synchronous pipelines are those in which the next stage of processing cannot proceed before the previous stage has completed. A pipeline stage becomes synchronous through waiting for the completion of ‘a job’, or for feedback to arrive. Usually an algorithmic constraint causes the completion of a job to stall. For instance, the processing of columns in a row-column 2D Fourier transform cannot proceed before the completion of processing all the rows. Many multi-step numerical analysis and signal- *processing applications have component algorithms with this characteristic. It is rare for all processing to stop at the same time even if the algorithm permits, as there will also be a synchronization overhead [go]. The presence of a single synchronous stage within a pipeline will affect all previous stages, in the sense that any reduction of latency will be lost at the synchronous stage. On the other hand, latency can be reduced if the remainder of a pipeline is asynchronous. Therefore, synchronous and asynchronous segments of a pipeline may be analyzed separately and the results combined. Fig. 2.4 is a classification of pipeline types. The classification is meant as guidance only, indeed some categories are omitted to avoid repetition. The category ‘algorithmic’ is not strictly a method of work allocation as it is possible to structure a decomposition into a set of independent functions organized either as a farm or a flow. The farm will be chosen as a way of load-balancing provided there are enough functions of suitable granularity.
PIPELINE
TYPES
25
for all forms
temporal
data-parallel
minimum
Fig. 2.4
maximum
Pipeline
types.
Synchronization might be constrained by the quickest function to complete. Speculative searcheshave this characteristic, e.g. [202]. 2.2.1
Asynchronous
PPF
In Fig. l.la, a simple pipeline without parallelization has already been informally examined. A simple pipeline is defined as one in which a single processor appears at each stage. This structure is now analyzed more formally to identify its mathematical characteristics. Fig. l.la showsjust one global maximum latency time though there might be a finite number of local maxima. It is the global maximum and its stage index that are of interest. Formally,
T
77lUX
e
bnax
= =
max({T(i),i argmin(l‘,,,
= 1,2,. . . ,s}) = T(i)),
(2 .1) (2 .2)
26
BASK
CONCEPTS
with {T(i)} being the set of maximum per-stage latencies and s being the number of stages. The performance parameters for a simple pipeline are latency
=
imazTmaz + k=i ?nlxE+1
throughput
=
(2 .4)
l/T,,,.
Fig. l.lb is a PPF in which there is pseudo-parallelism: no parallel decomposition has taken place. If enough processors have been deployed to prevent waiting at any stage, latency
=
(2.5)
T 0i
k i=l
throughput
=
Pi/W),
(= P2/w,
l
*a = PBIW),
where pi is the number of processors at stage i. Fig. l.lc, introduces parallel decomposition of individual tasks. pipeline in which no task waits =
p
(2.7)
Pl/T(Q*
(2.8)
T(4
):
Pi
i=l
throughput
=
For a
e
8
latency
(2 .6)
Equation (2.8) is most appropriate for geometric multiplexing. However, for some types of algorithmic parallelism the algorithm finishes when the first solution is found. If f(z) is the probability distribution function of the independent and identically distributed set of random variables {Xi, i = 1,2, . . . , p}, . with F(z) = JL nftyf (x)dx, then the minimum expected finishing time is given as q&J
=
P
x(1 - F(x))p-l
f (x)dx,
r -00
(2 .9)
which is a result from order statistics (see [269] or for an advanced treatment
Pa .
2.2.2
Synchronous
PPF
For a synchronous pipeline in which there is no waiting, define ind(i) =
0, if i is a synchronous stage 1, if i is an asynchronous stage,
(2.10)
2
(2.11)
which allows us to write latency
=
i=1
B(ind(i))T(i)
+ f:
ind(i)T(i)/pi,
i=l
with a() the Kronecker delta function. Throughput remains dependent on the rate that the pipeline can accept tasks.
DATA FARMNG
2.3
DATA FARMING
AND
DEMAND-BASED
AND DEMAND-BASED
SCHEDULING
27
SCHEDULING
As was remarked upon in the introductory section to this chapter, the data farm is the building block of PPF systems. A processor or data farm [235] is a programming paradigm involving message-passingin which a single task is repeatedly executed in parallel on a collection of initial data. Data farming is a commonly used paradigm in parallel processing [386] and appears in numerous guises: some (network-of-workstations) NOW-based [318]; somebased on dedicated multicomputers [373]; someconstructed as algorithmic skeletons [272]; and some implicitly invoked in parallel extensions of C++ [142]. A staple scheduling method for data-farm tasks is demand-based farming which gives the potential for automatic, run-time load balancing. To some extent a scheduling system is a compromise between generality and performance. Global optimization, which is a form of static scheduling, is at the performance end of the spectrum. Because global optimization is an NP-complete problem (mathematically intractable [139]), heuristics [loll are necessary, though all pertinent system characteristics should be taken into account. In some embedded systems, where the work-load is deterministic (constant), for example in repeatedly performing a Fast Fourier Transform, global optimization has a place within a data-farming regime. As optimization is time consuming, off-line partitioning of the work is usually required. In contrast, demand-based farming is a generalized method of scheduling. In demand-based farming, for which the number of tasks should greatly exceed the number of processes(processors, if each processor runs a single process), returning processed work (or a suitable token) forms the basis of a request for more work from a central ‘farmer’. The computation time of an individual task should exceed the maximum two-way data-transfer time from worker processor to farmer processor so as to hide communication latency. Initially, the central farmer loads all processorswith somework, which may be buffered locally, that is a static-scheduling phase. To avoid subsequent work starvation on some processes, no worker processor should be able to complete initial processing before the loading phase is over. Subsequently, after making a request, the worker should be able to process locally-buffered work while its request is answered. Linear programming has been used to predict a lower bound on the performance of data farms using demand-based scheduling [292], that is the performance beyond which it is not possible to improve due to the physical bounds of the system. The prediction assumesthat store-and-forward communication is employed, in which messagepassing is point-to-point and in which there is a handling delay at each intermediary node before the messageis forwarded. A further assumption was that task duration times are deterministic. However in [373], varying task durations were represented by mean values but the linear-programming technique was retained. Maximum performance was more closely estimated by including a number of overhead terms. In one version of the scheme [338], tasks were placed on workers in advance as if the
28
BASIC
CONCEPTS
distribution of tasks had been formed by demand-based farming. In theory, task granularity can be found by optimizing the governing equations for the model. In many cases, reported timings on unmodified regimes are accurate to 5%, which may well be more than adequate in our application domain where generality and scalability are as important as optimal performance. In Chapter 11, an alternative, more generalized, scheme of task scheduling is considered.
2.4
DATA-FARM
PERFORMANCE
CRITERIA
Introductory textbooks on parallel computing, e.g. [65], discussAmdahl’s law, and also point out that the fraction of sequential work f is a constant function in the law whereas in some applications f is a function whose value decreases with increasing problem size. Embarrassingly parallel, single-algorithm applications certainly have this characteristic. Algorithms in which there are multiple opportunities for parallel decomposition and a very small irremedially sequential component have attracted attention because of the ‘Grand Challenge’ awards [34]. However, in multi-algorithm embedded systems, while f may not be a constant function it certainly is not monotonically decreasing in value. Amdahl’s law has been revisited in [185]. Speedup is not a normalized quantity as [163] is at pains to point out. If a faster processortype is employed in the parallel system but the communication bandwidth remains fixed then the speedup will decline though the absolute processing time may well decrease. Therefore, a speedup measurement implicitly assumesa balanced system. Nevertheless, Amdahl’s law provides a useful ‘back-of-the envelope’ or first-cut estimate of the performance of a data farm. The extended example in Chapter 3 combines data-farm estimates to form an idealized performance estimate for a complete postcode-recognition pipeline. In some pipeline systems, sequential blockages within a stage of the pipeline can be masked by running that stage with one set of data in parallel with other stages of the pipeline, each processing different data. Of course, escaping the consequencesof Amdahl’s law is only possible because of the flow of data in a continuous-flow system. The performance of the pipeline is then found by finding the dominant stages across the pipeline. There are also more pessimistic laws, such as Minsky’s law or in [213], which state that speedup decreaseslogarithmically due to the added need to synchronize between parallel processes. A weakness of Amdahl’s law is that it assumesa perfect decomposition of any task, whereas it may not be possible to break a task into equal parts. If algorithmic parallelism is employed within a farm then it is unlikely that the computation of sub-algorithms will be balanced. A more likely scenario is that the same algorithm will run on each worker process but that data dependencies will result in different processing times. The different processing times may only be known in a statistical senseor indeed for some types of algorithm (e.g. searching algorithms) may
DATA-FARM
PERFORMANCE
CRITERIA
29
be unknowable in advance. At some point, the results of data processed in parallel has to be recombined. This may be after each stage of the pipeline (a synchronous pipeline) or the recombination may not need to occur until the results are finally output (an asynchronous pipeline) but surely recombination will take place. It is at this point that the synchronization overhead is incurred. Once a first cut estimate has been made then the estimate can be refined by accounting for the cost of communication. In the data-farm paradigm there is no global communication. The only communication takes place between farmer and workers. Similarly, across the pipeline the only form of communication which is not point-to-point is through feedback paths. However, as feedback to a farmer process occurs from a single source, that is another farmer, congestion does not arise. Congestion can nevertheless occur within a ‘single farm, particularly if the communication mode is store-and-forward. Because the design model is regular however (all farm workers will normally use the same communication model), it is possible to derive analytic estimates of upper-bound static performance [354]. As WaS mentioned in Section 2.3, a linear-programming technique can be used to deri ve the communication overhead. For example, if a processor farm is implemented using a buffered linear chain of N workers, then the maximum throughput achievable, MN, is given
bY ..
MN =
)1 N
1
TCALC
-
2TSETUP
4TSETUP
TCALC
+
%ET?JP
9
where TCALC is the calculation time (assumed identical for all work packets) and TSETUP is the CPU time required to set up the communication (the communication itself is assumed to occur autonomously). Similar expressions [353] can be derived for other topologies such as n-ary trees, resulting in a performance surface for varying numbers of processors, setup times, and calculation times. For small numbers of processors there is little difference in predicted performance for all forms of topology over a linear pipeline implementation. The linear-programming estimate is itself an idealisation as it assumes perfect buffering. However, it is not easy to fully buffer communications for image-processing applications where large data structures must be communicated, and this is the major reason for actual performance falling below the theoretical upper bounds. By contrast, the effect of setup times on the upper-bound performance is of secondary importance. Topology was a source of considerable academic debate when store-andforward communication was predominant amongst first-generation messagepassing machines [291]. With the advent of generalized communication methods such as the routing switch [305], the ‘fat’ tree [215], wormhole routing
30
BASK
CONCEPTS
[256] and virtual channels [78] the situation is less critical.5 Non-linear communication latency as a consequence is becoming less of an issue. The Bulk Synchronous Parallelism (BSP) programming model [236], which has been widely ported to recent machines, adopts a linear model of piecewise execution time, characterized by a single network permeability constant. Messagelatency variance can be reduced by a variety of techniques, such as the message aggregation used on the IBM SP2 SMP. Routing congestion can be alleviated either by a randomized routing step [364], or by a changing pattern of communication generated through a latin square. The asynchronous equivalent of BSP, that is the LogP model [69], likewise employs a linear model of communication. Even if communication overhead were constant however, there will always be a synchronization overhead. This issue is returned to in Chapter 11. As real-time exigencies must be met, asynchronous PPF systems do not normally have the luxury of postponed communication [159]. In the BSP programming model all communication takes place at a point of barrier synchronization. While this has advantages in tailoring the pattern of communication to the network, that communication is not overlapped with computation. Latency tolerance by ‘parallel slackness’ is also not always assumed to be possible in PPF. Indeed, even if multiple threads of control are available it would appear that the advantages of parallel slackness are bounded [7]. As in earlier systems [214], buffering is used extensively as a form of latency hiding in PPF.
2.5
CONCLUSION
As embedded applications grow in size and complexity, it has become apparent that a uniprocessor will be insufficient to cope with real-time processing requirements. However, there has been no systematic way of designing such applications to run across multiple processors. In contrast, there have been many attempts at making tasks already running on uniprocessors perform faster on parallel hardware. There are also parallel languages and environments but few attempts at guiding the design process. In essence, this is the same dilemma presented to users of object-oriented languages: there is a passive set of facilities but no guidance as to how to combine those facilities. Though recent attempts have been made to remedy this situation, the target application domain is not usually real-time, continuous-flow systems. In contrast, Pipeline Processor Farming is a systematic design method that attempts to cut the Gordian knot by reducing the design freedoms inherent
5The ‘fat’ tree topology proportionally increases bandwidth towards the root of the tree, with usually only the tree leaves performing computation. In wormhole routing, a message is segmented with the head of the message passing through an intermediary node without waiting as the remaining message segments follow, thus avoiding set-up time in intermediary nodes. Virtual channels emulate wormhole routing by software means on a store-andforward multiprocessor.
APPENDIX
31
in parallelism in favor of simplicity, practicality and consistency. PPF designs always result in a pipeline of some sort. PPF accepts the need to be able to mask a sequential bottleneck within a stage of the pipeline. However, any stage of a pipeline can be internally parallel, so long as a processor farm is used. A processor farm can take various forms, in the PPF model of parallelism, but the staple form of processing is data farming, which should be considered before opting for an alternative method. This is because data farming is the most generalized, scalable, and portable parallel-programming paradigm available.
Appendix
A.1 SHORT CASE STUDIES A number of systems are outlined here of the type suitable for a PPF approach. Reference [97] is a study of a parallel radar processing system for a phasedarray radar [330]. In such a system (Fig. A.l), by controlling the phase of individual elements of the array, beams can be formed at various elevations and directions. The Doppler effect is employed to detect motion in transverse directions, helping to remove clutter. As the beam rotates a new sector of the data must be processed to meet tight latency deadlines, requiring sufficient processing power to be available. A complete pipeline (Fig. A.2) consistsof: a phase-detection unit to extract phase and quadrature signals from incoming Doppler-shifted signals (hardware); an array of processorswhich process signals in order to remove clutter; and a final stage to identify the target types over time, requiring a global address space. The radar pipeline is largely asynchronous with a single flow of data (though some control information and correlation between adjacent beams is not shown). Multiple pipelines correspond to beams at varying elevations. The second stage of the pipeline was originally implemented with transputers but later adapted for more powerful 200MHz TI ‘C40 DSPs [349]. Multiple data farms are employed within the second stage. Data farmers are linked within this stage by an 1OOMhz Fibre Distributed Data Interface (FDDI) backbone [19] (the links of the transputer version operated at 20MHz), which allows scaling of communication bandwidth. Each data farm is responsible for a different range of returning pulses. Within a processor farm, the complete processing algorithm was performed by each worker, an example of temporal multiplexing in PPF terminology. The farm arrangement allowed the pipelines for lower beams to be scaled according to low processing requirements for these beams. However, the true advantage of this design is the ability to scale to differing clients, civilian or military. Traditional hardware designswith application specific integrated circuits (ASICs) are not only costly but also inflexible by comparison, though there is scope for ASICS, such as
32
BASIC
CONCEPTS
GEC Plessey PDSP1651OA FFT processor or PDSP16116/A complex multiplier, in processing regular algorithms [38] such as the Fast Fourier Transform (FFT).
Phased slow moving
Array
sea clutter
Radar
Fig. A.1
Multi-elevation
radar array.
,
returning radar pulses
w
PDU (sensor)
Beam Processing
w
Target
Update
Detection
of target
Unit /
f /
f
database
\
\
\
\
\
FDDI backbone
\ \
f
\
/
\
f
\
/
\
f
\
f
node 1
f
node 2
node n
f
f f
\ \
f
/
\
\
f
\ \
Each node is a data farm with upto
\
\ \
50 processors. Fig. A.2
Block diagram
of the GEC Marconi
Phased-Array
Radar System.
In [133], the AT&T array multiprocessor is configured as a pipeline in order to perform near (3 times) real-time speech recognition on a full-search algorithm. Though a pipeline, this design preferred a dataflow organization, not data farming. The pipeline is asynchronous with a single flow of data. In Chapter 10, a system based on an integrated recognition network is considered
SHORT
33
CASE STUDIES
though it is harder to achieve real-time performance and preserve full-accuracy on such a system. The DSP3 multiprocessor has a cuboid node topology (Fig. A.3), each node consisting of a cluster of DSP32 DSPs from AT&T. Figure A.3 shows the topology of a node sub-system upon which the speech-recognition pipeline was run, though with the intention of later scaling to the larger 128 PE topology. 5
6
I
I I
I
I
H
----
= host
I
one link sub-system
A, B = I/O DSPs 1 - 8 = clusters of 16 DSPs Fig. A.3
Topology
of the DSP3 multiprocessor
from AT&T.
A virtual pipeline with the communication topology of Fig. A.4 was super-imposed upon a node within the DSP3. Feature extraction from raw speech frames is accomplished on DSPs through standard signal-processing algorithms [295, 1791, and can be buffered if running ahead of subsequent stages in the pipeline. The compute-intensive parts of speech recognition are the calculation of the probabilities needed eventually to establish which of a number of candidates best matches the utterance. The latency of the system for real-time processing is given by the duration of speech frames which are typically 10 ms in length to avoid variations over time. Each incoming frame must be matched against all phone (sub-syllable speech sound) possibilities, the number of which increasesaccording to the vocabulary and the complexity of the grammar (perplexity). The AT&T system was tested on a vocabulary of 992 words with perplexity of 60, but vocabularies of at least an order of magnitude greater can be expected. After training from a set of representative utterances, a Gaussian mixture model is constructed for each phone to reflect variations in intonation. Figure A.5 shows a triphone model with just three mixtures (24 or more is realistic), denoted by unn with entry probability given by cnn. Each of the probabilities of entering a state must be updated for all current candidate utterances as a new frame enters, and there are also fixed probabilities for moving between states to reflect variations in time. The
34
BASIC
CONCEPTS
candidate utterances are then scored against a grammar (an application dependent set of possible phrases) at the phone, word, and phrase level. The throughput of the system is therefore given by the number of candidate utterances being examined at any one time, and will usually change with time as some candidates fall below an acceptable probability. Real-time speech recognition remains an interesting target for pipelined parallel systems.
0 TR
RI
Fig. A.4
I
\
The AT&T
all
LPC MIX PHN WRD
linear predictive coding (feature Gaussian mixture modeling modeline phone scoring word scoring
PHR TR
phrase scoring traceback
speech-recognition
vectors)
pipeline.
a22
a33
mixt 1 1 2
al2
a23
3
state-
3
2
Fig. A.5
Simplified
Gaussian
mixture
model.
The work in [53] is an early parallelization of the H.261 video codec by purely software means. Though specialized VLSI chip-sets have been developed for the standard codecs [37, 1301,there is always a period of experimen-
SHORT
CASE STUDIES
35
tation when the algorithms are prototyped within the context of a complete system. Testing is a lengthy process unless a parallel implementation is developed. Figure A.6 is a block-diagram of the H.261 hybrid predictive/transform coder? The H.261 encoder is given fuller treatment in Chapter 8 and a parallel implementation of the simpler H.261 decoder has already been described in Chapter 1. H.261 is typical in layout and algorithmic content of a series of other codecs stemming from motion JPEG, through MPEG-1 & -2, and now H.263+ and H.263L. MPEG4 is of a different nature, building on model-based coding, and will no doubt go through a prototyping phase.
Source Picture + I v
Encoded 1-1 I
I
-1 I‘
, ,
I
I
Motion I 1Compensate 1
Motion Compensated Previous Frame
. -*--a- 1 Length Coder
1
Motion Vectc rs I
Buffer I
Motion W Estimate
Fig. A.6
)F Output Bitstream I
Previous Frame
Block diagram
of the structure
, Frame Delay
of the H.261 encoder.
In such codecs, it is found that motion estimation (ME) takes up from 60-70% of computation [87], followed by calculation of the discrete cosine transform (DCT) across 8 x 8 pixel blocks of the video frame. The basis of parallelization of ME by geometric multiplexing is also by blocks grouped in units of four blocks called macroblocks. Reference [53] adopted a single data farm with static work scheduling, rather than a pipeline and rather than employ demand-based work scheduling. To avoid overflow of the output channel, the quantization coarsenessis varied, normally requiring feedback. In fact, the quantization level is estimated by the farmer on receipt of processing mode information on a per macro-block basis from the worker processes. The estimate is broadcast so that the second phase of processing can proceed. 6The decoder is incorporated into the encoder in order to reconstruct the encoded image which is then subtracted from the new incoming frame, thus giving rise to a predictive error signal.
36
BASK
CONCEPTS
Therefore, this data farm works in synchronous fashion. However, notice that this implementation feeds back the quantization level without waiting for the variable-length encoder (VLC) to complete. Figure A.7 shows the parallel implementation, which with the technology of the time (transputers) had a throughput of 2 QCIF (188 x 144 pixel) frames/s.
video frames
frame grabber
packetised bitstream
ISDN interface b
Fig. A.7
H.261 video coding system.
> worker 2a
3 PPF in Practice In this chapter, a detailed case study is provided. The automated recognition of handwritten postcodes is a classic soft, real-time system for which PPF is ideally suited. Chapters 8-10 provide further case studies illustrating the advantages and disadvantages of the PPF method. In the United Kingdom (UK) postal system, postcodes are often handwritten onto envelopes ready for posting. When the envelopes arrive at the sorting centre, they are placed on a mechanical conveyor belt. The task of the recognition software is to identify the postcode ready to stamp a corresponding phosphorescent code onto the envelope when it reaches the end of the belt. The phosphorescent code is subsequently used for sorting the envelopes in later sorting machines, right down to the I.evel of the individual postman ‘s delivery round. There are no hard deadlines to be met , because there are no safetycritical factors at play. Nor are there asynchronous interrupts to respond to from peripheral or sensor devices. Nevertheless, there are throughput and latency targets to be met, defined by the speed and length of the conveyor belt. In [258], this postcode recognition application is included as a typical, soft, real-time system alongside classical hard, real-time system examples. UK postcodes consist of variable length words consi .sting of 5 to 7 alphabetic (A.) and numeric (N) characters. The postcode can be subdi .vided into two parts; an initial outward code of two to four alphanumeric characters and a final three-character inward code. The outward codes correspond broadly to postal towns but some large towns and cities might have several different postcodes defining different areas. The inward code refers to a part of a street or a building. The outward codes are of primary concern and can be in any of the following six formats: AN, AAN, ANN, ANA, AANN, AANA. 37
38
PPF IN PRACTKE
The inward code always has the format NAA. Unlike postcodes in use in other countries (such as the fixed-length numeric codes used in the United States and Australia and the alphanumeric, fixed format codes used in the Netherlands and Canada), the variable length and format, alphanumeric postcodes used in the United Kingdom are not easily distinguishable from some place names, and are therefore relatively difficult to extract from the other address fields.’ To avoid this problem, in this work the address and postcode were each written within preprinted boxes on the envelopes, though pre-printed envelopes are not currently widely used in the United Kingdom.
3.1
APPLICATION
OVERVIEW
Handwritten postal address recognition is a typical multi-level knowledgebased vision application. Real-time OCR systems for recognizing printed addresses are widely used by the postal services, but systems capable of recognizing handwritten postal addresses (15-20% of all mail [285]) have only recently achieved the recognition performance and the throughput required for commercial application (the work reported here was carried out in the early 1990’s). postal adFigure 3.1 shows a top-level block diagram of the handwritten dress recognition system, which can be broken down into two independent and inherently parallel pipelines of components. One of these attempts to recognize the characters within the postcode (from which a corresponding address can be determined using the UK postal address database) while the other simultaneously extracts features which are used to verify the address predicted from the postcode. If the verification features match the postcode address prediction sufficiently accurately, the address is accepted; otherwise the mailpiece is rejected for manual sorting. Full details of the vision algorithms used within the postcode and address verification pipelines are in [89] and [156] respectively. In this particular application, the system design specification is that 10 envelopes/second must be processed by the machine. Furthermore, the size of the computational pipeline is limited by the associated mechanical conveyor which is specified as having a maximum capacity of 90 envelopes (i.e. 9 seconds latency). An ordering constraint also exists, in that results from the OCR system must emerge in the same sequence that the mail-pieces were scanned, to ensure correct phosphorescent dot coding of each envelope with its corresponding postcode. Since the postcode recognition and address verification pipelines shown in and independently, each can be parallelised Fig. 3.1 can operate concurrently
1As an examp 1e, the postcode ‘E5 5EX’ and the county name ‘ESSEX’ valid postcode and county name which could easily be confused.
are respectively a
PARALLELlZATION
separately, throughput
Postcode
recognition
pipeline -----------------------
i Postcode II ) Classification +- preprocessing I I I I I L_______------------------------------------------________----------------------------~~~~ I
+
Dictionary Search ------.I
’ I* I
Address pre-processing
*
Address
verification
Fig. 3.1
Implementation
I [ Reference 1 features I I I I II I
39
Feature extinction
address
V
Verified postcode
Matching
I I I
I I
3.1.1
RECOGNIZER
and their processing speeds may be balanced to meet the overall and latency specification.
r--------------------------------Postode image
OF THE POSTCODE
> I I
pipeline
Post all OCR system.
issues
The address recognition system was originally implemented as a sequential simulation algorithm on a Sun SparcStation [155]. It was then ported to a single T800 transputer running on a Meiko Computing Surface (CS2), a transputer-based multiprocessor [356], which was usedto obtain the execution profiling data presented below. All initial parallelizations were implemented using Meiko’s CSTools parallel programming environment. This provides a library of C functions for implementing virtual channel communication between arbitrary pairs of processors, whether or not they are physically directly connected. A further library of functions (CSBuild) which run on the host processor (a Sun workstation), allows a custom loader program to be written which configures and then loads and runs a network of processors. In the case study examples presented below the CSBuild loader program reads parameters from the command line which define the overall pipeline configuration and specify the number of worker processors to be configured within each processor farm. This allowed practical results to be rapidly obtained for a large number of different PPF configurations, as shown in the results graphs below.
3.2
PARALLELIZATION
OF THE POSTCODE
RECOGNIZER
The OCR algorithm for handwritten postcodes utilizes character features proposed in the characteristic loci algorithm [190] (preprocessing stage) combined with a quadratic classifier (classification stage). Ranked lists of characters at
>
PPF IN PRACTlCE
40
each postcode character position are then pruned by applying postcode syntax rules. The n (n 5 5) highest ranked characters remaining in each postcode character position after applying the syntax rules are then permuted to form n6 (6 character postcodes) or n7 (7 character postcodes) possible postcodes which are presented to the dictionary. Postcodes which are matched in the dictionary are sorted according to an overall match function derived by multiplying the matches for individual characters, and the addresses corresponding to one or more best matched postcodes are retained for verification against features extracted from the handwritten address. It is necessary to introduce some limited data parallelism (splitting the processing up by a data division, though subsequent load balancing can be dynamic or static) in order to meet the application latency specification of 9 seconds, since although speedup can be achieved using temporal multiplexing alone (i. e. retaining the original processing granularity), temporal multiplexing has no effect on latency, and the latency of the original sequential algorithm was 10.5 seconds. Conversely however, temporal multiplexing requires less parallel design effort than either data or algorithmic parallelism, hence the design objective was to introduce only as much data or algorithmic parallelism as necessary to satisfy the specification. Since some parts of the application are inherently sequential, the overall application must be partitioned so as to separate these parts (which can only be speeded up using temporal multiplexing) from other parts to which data and/or algorithmic parallelism can be applied. In the following section, possible partitioning points for the postcode recognition algorithm are identified by considering what forms of parallelism can be applied to each algorithm component. 3.2.1
Partitioning
the postcode
recognizer
Table 3.1 summarizes the average processing times for the major functions within the postcode recognition algorithm, and is derived from sequential execution time statistics obtained while running the algorithm on 100 address images of data on a single processor. As can be seen from the table, the preprocessing and classification tasks exhibit almost the same computational complexity and are three times slower than the dictionary search algorithm (measured for n = 5). The decomposition of the system into a pipeline of processor farm stages can be carried out as follows: l
This is composed of five basic tasks as shown in Table 3.1. Due to the sequential nature of the tasks, algorithmic parallelism is not feasible, but data parallelism can be implemented at the level of postcode characters or character features. Since the features for each of the characters need to be combined before the classification stage takes place, it is necessary to implement classification on a different processor farm from preprocessing if different levels of parallelism are exploited Preprocessing.
PARALLELlZATlON
OF THE POSTCODE
RECOGNIZER
41
in the two stages. In the implementation described below, both feature extraction and classification exploit character-level parallelism, however each stage was implemented as a separate processor farm to allow a future upgrade to the use of feature-level parallelism within the preprocessingstage if necessary (this would potentially reduce latency further). l
Classification.
This comprises three algorithms:
1. transformation of the features into quadratic space; 2. location of the region where the classeslie in quadratic space; and 3. production of a ranked list of postcode characters. Again algorithmic decomposition is not applicable, and in this case data parallelism can be implemented only at the character level. Since the ranked lists of characters need to be combined before presenting them to the dictionary stage, it is necessary to implement the classification and dictionary stages on different processor farms. l
Dictionary. This involves application of the syntax rules (a table lookup operation), generation of all possible postcodes from the remaining ranked lists of characters, and a trie search [191] in the postcode/address dictionary. 2 A form of algorithmic parallelism can be applied here by dividing the full postcode dictionary into six sub-dictionaries corresponding to the six possible UK postcode formats, but in the implementation reported below temporal multiplexing alone was applied to this stage.
By introducing character-level data parallelism to the preprocessing and classification stages, the latency of these stages should be reduced by a factor of between 6 and 7, leading to an overall mean latency of lessthan 3 seconds (ignoring communication overheads). The implementation below therefore describes a design which utilizes data parallelism in the first two pipeline stages and temporal multiplexing alone in the final dictionary stage. The performance for this implementation is then compared with that of an implementation which utilizes temporal multiplexing in all three stages. 3.2.2
Scaling
the postcode
recognizer
Parallel implementation of the system was performed in two steps. Firstly, parallel versions of each stage were implemented independently, to enable the 2A trie search is an efficient character-by-character tree search. However, search speed has subsequently been improved by an order of magnitude through the use of a novel semantic neural network (SNN) [225] dictionary method. The replacement of the original dictionary search algorithm by the SNN alternative would of course require re-balancing the PPF, exactly the sort of iterative development which the methodology is intended to accommodate.
42
PPF IN PRACTICE
dynamic scaling performance of each stage to be measured. Then the overall system was integrated by configuring the stages into a pipeline. Fig. 3.2 shows a plot of throughput (postcodes per second) performance measured against number of processors for each independent pipeline stage for the case where character-level data parallelism has been utilized in the preprocessing and classification stages, and temporal multiplexing alone in the dictionary stage. Tab/e 3.1 Average Execution Times for the Functions in the Postcode Process and Data Packet Sizes Communicated Between the Stages Process
Preprocessing
Classification
Dictionary
Function Filtering Feature Feature Feature Feature Total
Average Time (second/image)
extraction concentration unification counting
0.650 1.170 0.220 1.640 0.790 4.470
Quadratic space transformation Character classification Ranking calculation Total
0.007 4.400 0.040 4.447
Search Sort Total
1.500 0.004 1.504
Recognition Data Packet Size (bytes)
2112
33
82
The plots reveal a number of important points: l
The throughput achieved by each stage scales incrementally and fairly linearly up to the maximum number of processorsavailable in the Meiko system (32). At this limit, the dictionary stage is at the required throughput level, and the other two stages are operating at just over half the specified throughput. Further increases in throughput could be achieved at each stage if more processors were available, as no stage is close to saturation of its communication links.
l
The throughput of the dictionary stage scales less rapidly than might be expected from the static profiling statistics of Table 3.1. This is because the execution time for this stage is an average of a strongly bimodal distribution (see Fig. 3.3), as ?-character postcodes take about five times as long as 6-character postcodes to process in the dictionary. The large variation in execution times leads to queueing delays at the output of the dictionary, since postcode ordering within this stage must be preserved. This degradation in the performance due to the wide
PARALLELIZAT/ON
OF THE POSl-CODE
RECOGNIZER
43
12 10
preprocessing -+classification * dictionary +--
8 Throughput
6
5
Fig. 3.2 Throughput recognizer .
lo 15 20 25 Total number of worker processors
graphs
achieved by scaling individual
30
stages of the postcode
distribution of processing times in the dictionary stage can also be predicted theoretically [353]. l
For a given throughput, Fig. 3.2 allows the required number of processors in each stage to be estimated so as to achieve a balanced and efficient PPF implementation.
The full postcode recognizer PPF consists of a pipeline of three ternary-tree processor farms. Each processor farm comprises a farmer process on a master processor which receives data from the previous stage (from the input device in the case of preprocessing) and distributes it over the worker processeson the other processors allocated to that stage. As soon as a worker finishes processing, it returns its results to the farmer, which forwards them to the next stage and sends new data to the worker. In the first two stages, where data parallelism is exploited, each work packet comprises the data required to process a single postcode character; in the dictionary stage each work packet consists of the ranked list of character matches for a complete postcode. 3.2.3
Performance
achieved
Speedup, throughput and latency of the overall PPF were measured by first choosing fixed and equal number of processors at the preprocessing and classification stages (as required from Fig. 3.2). The number of processors in the dictionary stage was then chosen as the independent variable because of the large divergence between static and dynamic scaling predictions for this stage.
PPF IN PRACTICE
25 Frequency
20 t
0.5
Fig. 3.3 Distribution recognizer .
1
1.5 2 2.5 Time (sec.)
of execution times for the dictionary
3
3.5
search stage of the postcode
Example speedup graphs are shown in Fig. 3.4 for the casesof 3, 5,7,9 and 11 worker processorsin each of the first two pipeline stages. Each graph shows how the speedup varies with the number of workers in the dictionary stage, for the specified number of workers in the other two stages. The ideal graph is a line of gradient 1 which represents a parallel implementation in which all processors operate at 100% efficiency. In reality, efficiency will be less than 100% due to processor overheads such as the farmer’s housekeeping operations for each stage, variability of execution time for different work packets, and communication overheads. The general form of each speedup graph is similar: as the number of processors in the dictionary stage is increased, the achieved speedup also increases until saturation occurs when the dictionary stage no longer limits the pipeline throughput. Optimum efficiency occurs at the point where each graph most closely approaches the ideal graph; at this point, the pipeline is balanced. For the graphs shown, balanced pipelines are achieved with 9 (3+3+3), 15 (5+5+5), 19 (7+7+5), 25 (9+9+7) and 29 (11+11+7) workers, and correspond to efficiencies of 53.3% 58.7%, SO%, 64.8% and 66.9%. The gradual increase in efficiency is a result of the farmer overhead decreasing as the size of the processor farm increases, and would eventually decline again as communication saturation is approached. Figure 3.5 compares the throughput of the complete 3-stage PPF postcode recogniser described above with a similar alternative implementation which utilizes only temporal multiplexing in each of the three stages. Both implementations achieve linear throughput scaling as long as the numbers of workers in each of the three processor farm stages are maintained in balance,
PARALLELlZATION
OF THE POSTCODE
RECOGNIZE!?
45
I ideal -L& 25 Speedup
20 15
15 20 25 10 Total number of worker processors
5
Fig.
3.4
Speed-up
graphs for the postcode recognition
pipeline.
but the PPF implemented solely using temporal multiplexing achieves slightly greater throughput for two reasons: The fixed overhead of header information in each communication packet means that more data must be communicated in total when the data stream is divided into character-based packets than when it is divided into postcode-based packets. Splitting the postcodes up into individual characters and processing them independently increasesthe ordering constraints, as the ranked list of characters at each postcode character position must be recombined into postcodes at the dictionary searching stage before any processing starts in this stage. The main advantage of introducing data parallelism into the implementation is that it decreasesthe latency of the pipeline, as is shown in Fig. 3.6 which indicates the latency measured (in seconds) for the two different implementations. The latency of the postcode-parallel implementation remains constant regardless of the number of processors since there is no sub-division of either the data or the algorithm in this implementation. In contrast, the latency of the character-parallel implementation decreasesas more processors are added until sufficient processors are available to fully exploit the data parallelism in the design (7 workers in each of the first two pipeline stages). For PPFs with sufficient processors, the latency of the character-parallel implementation is 3.2 seconds whereas it is 10.8 seconds (i.e. the same as for the original sequential application, but with additional communication overheads) for the pure temporal multiplexing approach. Hence the introduction of some limited data parallelism into the implementation makes it possible
46
PPF IN PRACTlCE
2.5 character-parallel + postcode-parallel &
Throughput
n
10
Fig. 3.5 Throughput ognizers.
15 20 25 Total number of processors
graphs for character-parallel
and postcode-pmillel
30
postcode rec-
to satisfy the latency specification for the system, at the expense of a slight decrease in throughput and efficiency.
12 10 character-parallel + postcode-parallel -A--
8 Latency
6 4
10
Fig. 3.6 nizers.
Latency
15 20 25 Total number of processors
graphs for character-parallel
and postcode-parallel
30
postcode recog-
PARALLEllZAl-ION
3.3
PARALLELIZATION
OF THE
ADDRESS
OF THE ADDRESS
VERIFIER
47
VERIFIER
The redundancy between the postcode and the remainder of the address is exploited by extracting features of the addresswhich are then matched against one or more candidate addressescorresponding to the postulated postcode and derived from the UK postcode/address database. The verification process consists of two major stages: 1. Preprocessing. Address images are processedto extract first the addresslines, then the addresswords, and finally, a slant correction process is performed on each address word to minimize variations in the features relative to the slant of the handwriting. 2. Feature extraction. A number of algorithms are applied to the address word imagesto extract predefined global and local features, which include initial and final characters of words, loops, and ascender/descender sequences. The final stage of the complete address recognition system matches features extracted from the addressimage against corresponding features derived from the reference addressesfound by the dictionary search. If a sufficiently high match is found, then the postcode is accepted otherwise it is rejected. This matching process is around lo3 times faster than the other algorithms described above, therefore parallelization effort was concentrated on the preprocessing and feature extraction stages of verification. Preprocessing and extraction of verification features is roughly 10 times more computationally expensive than postcode recognition, and the volumes of data communicated between stagesare also correspondingly larger, because verification utilizes the full address image, whereas postcode recognition only operates on the constrained postcode image field. 3.3.1
Partitioning
the address
verifier
Figure 3.7 shows that the preprocessing and feature extraction stages of the address verification algorithm can be broken down into a pipeline of four independent stages, and gives the average sequential execution time on a single processor for each stage, and also the amount of data communicated between the stages. 1. Line extraction. At the line extraction stage, image processing operations are applied to the complete address image: parallelization can therefore best be achieved by temporal multiplexing. The input data to the task is the complete address binary image, and the output data is a set of up to five address line binary images. 2. Word extraction. Word extraction operations are applied to each line of words in the address separately, hence line-level data parallelism can
48
PPF IN PRACTICE
be readily exploited in this stage as well as temporal multipl .exing. The output data from this stage is a set of up to five binary word images per line. 3. Slant correction. Slant correction is applied separately to each word image extracted by the previous two stages, hence word-level or linelevel data parallelism is easily exploitable here in addition to temporal multiplexi .ng. Both input and output data consist of a set of independent images of each word in the address. 4. Feature extraction. Feature extraction consists of four independent algorithms (character segmentation, word case classification and ascender/descender detection, character recognition and loop detection) which are configured as shown in Fig. 3.8. Word-level data parallelism is again available at this stage, but in addition algorithmic parallelism can also be exploited, since up to three tasks can be performed concurrently (corresponding to the three independent branches).
Address
Word 10.13
extraction s/address
Slant correction 20.11 s/address (3.63 s/word)
Data packet 75 Kbytes
Slant corrected y words Feature extraction 52.03 s/address (11.15 s/word)
Data packet 75 Kbytes
Features
Fig. 3.7 Functional block diagram of the address verification
system.
PARALLEL1ZAT/ON
, r’--“--”
1 1 I ’ 1 1 1
I I I I I
I
“-“-‘-“““““‘(
I I I I I I I
I I
I
I I I
;
r-------
I
’ I
i Process 1
First character segmentation 0.30 s/word
Process 2 ’
,$
;‘I
I I II I I I I I I I I I I I I I I I I I I I t
1
I
1 1 'I ’ ’ 1 1 1 I
I I f I I I I I
0.26 s/word
Ascender/ descender detection 2 -23 s/word ----
49
--------------
1 l l 1 f I
Process 3
l l l
l
Last character
l l
I l l l l l l l 1 l l l l l l l l l l f
L I First character recognition 4.36 s/word
i / I I I f I@ I I I I
l l l f 1 l l l
: : I I I I I I I
l l l 1 1 l I
----
-- ---- ------
I
1 Features Fig. 3.8
3.3.2
Scaling
Functional
the address
block diagram
I I I I I I I I
First character i images
l l l
ii A
! !1
i L I f I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I L--
I I I I I I I II I I I I
I
:
VERIFIER
1 Address word images
-““-“‘,
I
OF THE ADDRESS
of address feature extraction.
verifier
The partitioning above initially suggeststhat a pipeline of four independent processor farms with worker processors provided for each stage in the rough ratio 3:1:2:5 will achieve approximate throughput balance within the pipeline, and provide maximum opportunity to exploit data parallelism, and thus minimize pipeline latency. In practice however, it was noted that by combining the word extraction and slant correction stages, a simpler three-stage pipeline could be achieved in which static balance occurs for worker processors in the ratio 3:3:5. The results reported below are for this configuration, in which temporal multiplexing alone is applied at the first stage, line-level data parallelism and temporal multiplexing at the second stage, and algorithmic parallelism, word-level data parallelism and temporal multiplexing at the final stage. It should be apparent that several other processor configurations are also possible.
50 3.3.3
PPF IN PRACTKE
Address
verification
farms
The address line and address word segmentation farms exploit temporal multiplexing and data parallelism and are conceptually similar to the postcode recognition farms described earlier. However, the address feature extraction stage combines data parallelism (the complete address is divided into individual word images) with algorithmic parallelism (workers execute one of three different algorithms, as shown in Fig. 3.8), and therefore operates in a somewhat more complex way than any of the processor farms previously described. For simplicity, the algorithmic parallelism is distributed statically, by allocating one third of the total processors in the farm to each of the three required algorithms (each process has roughly similar static computational complexity). The farmer on the master processor therefore has to buffer the input word image data, since the same data is sent to two of the three algorithmic processes. The first worker processreceives word imagesfrom the farmer and performs loop detection. The number of extracted loops is returned to the farmer. The second worker process receives the same word images from the farmer and performs the first character segmentation, word case classification and ascender/descender detection, last character segmentation and recognition tasks. It returns the ascender/descender sequence or the recognized last character in ranked order, depending on whether an uPPer upper case or mixed case word was detected. This worker process is also responsible for transmitting the first character of the word image after the segmentation process to the third worker process. Finally the third worker process receives the first character of the word image from the second worker and performs character recognition on it. Recognized characters in ranked order are returned to the farmer. 3.3.4
Overall
performance
achieved
The full address verification PPF was built by connecting the three stages described above in a pipeline configuration. The performance of the verification pipeline was measured by fixing the number of processorsin the first two stages and varying the number of processors at the feature extraction stage, as shown in Fig. 3.9. In this figure, the ‘ideal’ graph represents the speedup if perfect buffering between stages were obtainable and communication overheads could be ignored, but the residual sequential overhead of each pipeline stage’s farmer distributing data to its workers is taken into account by applying Amdahl’s law [16]. Three sample practical speedup graphs are also shown; these represent parallel configurations in which 3, 5 and 7 worker processors are utilized in each of the first two pipeline stages, and the number of workers in the final stage is then varied. As can be seen, for each configuration, the performance increasesfairly linearly as additional processors are added to the final stage, until that stage no longer limits throughput, at which point adding further processors has no effect. Thus the speedup scales incrementally with
MEETING
THE SPECiFICATlON
51
the number of processors used, achieving a maximum of about 15 with 26 workers (29 processors total), an efficiency of 52%. Figure 3.10 shows that the throughput achieved with optimal PPF configurations also scales fairly linearly up to 29 processors, but at this level it is still about 80 times slower than the required real-time performance specification.
ideal 3,3,x 5,5,x 77 1 tX Speedup
5
Fig. 3.9
3.4
Speed-up
MEETING
10 15 20 25 Total number of worker processors
graphs for the complete address verification
pipeline
THE SPECIFICATION
The maximum speedup achieved for the verification pipeline was 15 with 29 processorsin total, and in this casethe throughput (0.12 address/second) and latency (58.7 seconds) specifications are still far from being met. More significantly, only a limited increase in speedup could be achieved by adding more processors, becausethe communication channels saturate with 15-25 workers in each processor farm. In reality, it is not surprising that the specification has no chance of being met by the verification PPF, as this would require a speedup of around 103, which is well beyond the practical scaling range feasible using this technique. Future attempts would require more recent generations of processors with higher communicate to compute ratios. For the postcode recognition pipeline, an overall maximum throughput of just over 2 postcodes/second and mean latency of 3.2 seconds were achieved with a PPF of 32 processors (29 workers and 3 farmers). These results correspond to a speedup of 21.4 for the application as a whole, and an overall processor efficiency of 66.9%. As no stage is close to communication saturation, it was concluded that simply by introducing more powerful computa-
52
PPF IN PRACTICE
tional engines to augment or replace the processor the specification could be fully met. The remainder of this section describes a port to an eight module Paramid machine [352], where each computational node consists of one Inmos T805 transputer and one Intel i860-XP microprocessor [22, 119, 2861. The i860 acts as a high-performance computational engine allowing the transputer to become a dedicated communications co-processor. In our implementations, transputers also took the role of master processorshosting the farmer processes, distributing work packets to workers, so that it was possible to configure a maximum of 3 pipeline stages with up to 8 workers in total.
0.14 0.12 01. Throughput 0.08 0.06 0.04 0.02 0 5
Fig. 3.10
Throughput
10 15 20 Total number of processors
scaling graph for the complete
25
address verification
pipeline.
Unlike the prototype implementation on the Meiko CS, buffering was used both locally at the interface between each i860 and transputer and globally between each stage of the pipeline. The former buffers are needed to ensure that the i860 does not wait for the transputer and the latter are used to ease flows along the PPF. In particular this reduces the bottleneck at the dictionary stage where there is a bimodal computation time distribution (Fig. 3.3). The best number of slots in all local buffers was found to be at least ten. As in the earlier implementation, the Paramid implementation utilized data parallelism in the preprocessing and classification stages and temporal multiplexing in the dictionary classification stage. Table 3.2 shows the throughput and latency achieved with an optimal 4:3:1 configuration of 8 processors overall within the pipeline, and confirms that with this configuration both the throughput and latency specifications for postcode processing are met. The demand-based farming method timings now show an increase in throughput, because of the added flexibility.
CONCLUSION
Table 3.2
3.5
Throughput
and Latency
Number of Postcodes
Time (s)
100 200 300 400
9.23 17.93 25.89 35.11
of the Postcode Recognition
Throughput (postcode/s) 10.83 11.16 11.58 11.39
Mean Latency
S.D.
1.81 2.11 2.14 2.23
0.29 0.37 0.32 0.33
53
Pipeline.
CONCLUSION
The postcode recognition example’s key feature when viewed as a system is the comparative ease with which the design can be incrementally scaled so that a given performance can be attained. When performance limits of a particular hardware solution are encountered, the design can also be easily transferred to alternative hardware. In the present climate of technological change (by virtue of Moore’s law), order of magnitude advances in processor performance will occur roughly every five years. By capturing the design as a generic PPF solution, hardware changes can be accommodated without completely rewriting the software.
Appendix A.1
OTHER PARALLEL
POSTCODE
RECOGNITION
SYSTEMS
A number of other parallel handwritten postcode systems have been developed, and to some extent the PPF application is a synthesis of these systems. The commonalty of these approaches reinforces the need for a standard development methodology. In [182] a transputer-based automatic handwritten postcode reading system is described. The distinctive feature of the Dutch postal system is that the postcode (4 digits followed by 2 letters) is normally written in boxes preprinted on envelopes or postcards. This makes it easier to locate the postcode and segment the individual postcode characters and thereby reduces the complexity of the image segmentation process. The postcode recognition algorithm consists of six steps: 1. Connected component labeling; 2. Location of postcode boxes; 3. Elimination of postcode boxes; 4. Segmentation of postcode characters;
54
PPF IN PRACTICE
5. Recognition of individual characters; and 6. Verification of the postcode’s existence. In order to achieve the required throughput, the algorithm was parallelised on a processor farm architecture of 36 T800 transputers. The input to the system is the scanned address image. If the postcode is identified, it is printed on the envelope as a fluorescent bar code by the machine. The mean processing time for one address image on a T800 is 3.3 seconds. By applying address-level parallelism, a throughput of around 10.8 items per second was obtained. This implies a speedup value of around 35 with an impressive efficiency factor of 9’7%. However detailed information about the parallel implementation has not been described elsewhere. Reference [323] proposed a parallel pipeline architecture based on transputers for real-time OCR applications, such as recognizing scanned documents including handwriting, typescript and figures. The OCR machine consists of two basic modules: character recognition and linguisti .c analysis. The recognition unit comprises four stages: (1) preprocessing, (2) segmentation, (3) classification, and (4) recognition. In the linguistic analysis stage, the letter alternatives output from the recogniser are combined to form a number of letter strings. These candidate words are then checked against a trie dictionary which accommodates up to 70,000 words. After word look-up, syntax rules are applied to filter out the words which are not acceptable grammatically. Meanwhile, a semantic analysis is carried out to select from the list of words by using the information about the meaning of the words. The results from the semantic and syntax analyzes are then combined to reconstruct the words. The system architecture is a pipe1ine of five tasks. It is reported that real-time performance using this system was achieved, but performance results such as speedup and efficiency were not quoted. Itamato et al., [174] introduced NEPLOS (NEC’s Pipelined Parallel OCR System) for postal mail sorting. The system consists of eight basic functions: (1) address block location, (2) line segmentation, (3) character segmentation, (4) normalization, (5) character determination, (6) address collation, (7) address recognition, and (8) postal code recognition. A previously-designed machine used a pipeline architecture with processors allocated to each function according to the load and the capacity. However, improvement in processing speedas well asthe extension of readable content (e.g. handwritten addresses) was required. Therefore a new multiprocessing architecture was designed which consists of a main central processing unit (MCPU) and a number of recognition processing units (RCPU). Each RCPU has the capability to recognize the postcode and address on mail items independently of other RCPU’s. The MCPU controls the status of the RCPU’s and performs scheduling of RCPU’s upon request. All functions requiring high-speed processing, such as histogramming, image labeling, feature extraction and pattern collation are implemented using specially designed hardware. It is reported that up to 128 RCPU’s can be connected in parallel, but further processing capacity can be
OTHER
PARALLEL
POSTCODE
RECOGNITION
SYSTEMS
55
achieved by adding more OCR engines. With the new machine, a reading capacity of 20 times that of the previous system was achieved and a processing speed of approximately 9 items per second for address reading can be expected. Reference [43] presents a transputer-based system for the recognition of handwritten zipcodes. The system consists of preprocessing, zipcode location, zipcode segmentation, zipcode recognition, and zipcode decision. Using a pipeline architecture and implementing either geometric or algorithmic parallelism it was estimated that a processing speed of up to 9 items per second would be obtained with sufficient transputers. Reference [62] describes a parallel architecture called EMMA2E for postal applications developed at Elsag Bailey Inc. This is an improved version of the proprietary commercial EMMA2 multiprocessor which was delivered in 1987. The new architecture differed from its predecessor in that heterogeneous PEs were developed to satisfy the requirements imposed by the applications involved. Therefore, EMMA2 has a very different architecture to PPF systems. The architecture is built on various hierarchical levels. For each level, there is a physical communication channel (bus) which makes data exchange possible. At the lowest level there is the PE which is the computing unit present on all active modules. It is stated that different types of custom and commercial co-processors (e.g. DSPs) can be used as PE co-processors. The next level is called PN32 which is the multiprocessor module of the architecture and has four PEs. Above this level there are two higher levels called FAMILY and REGION. These are multi-port levels and allow connection between PEs located at different modules. The architecture is designed to have a throughput rate of lo-13 mail pieces per second for typewritten addresses. The research reported in [350] describes a multi-grain parallel architecture, ArMenX, specifically designed for implementing neural networks. Again this architecture is very different from a PPF architecture. The processing sequence of the system is letter digitization, zipcode extraction, zipcode segmentation, digit recognition, zipcode assembling and verification. The parallel architecture is intended to implement neural networks for the recognition of five-digit numeric French zipcodes. The architecture is organized into three processing layers. The upper layer is built using five Inmos T805 transputers. The middle layer, the so called Programmable Logic Layer, consists of network of FPGAs and offers very fine-grain parallelism structured as a high-bandwidth communication processing ring. The bottom layer is constructed using five DSPs. The first Transputer receives the whole postcode, picks up the last postcode digit and sends the others to the next node. Each transputer proceeds in the same way. When the digit has been received in a transputer, it communicates with the DSP and the digit is loaded in the DSP’s memory. Next, the DSP unpacks the data and performs the recognition algorithms. As the recognition is completed, the DSP generates an interrupt to the transputer. The former reads the result and spreads it to the previous node. Finally, the head transputer concatenates the five digits.
4
of PPF Applica tions
Development
Previous chapters have described the way by which a first-level PPF design is executed. However, software development requires more than a design. It This chapter gives an requires a systematic way of constructing software. overview of the PPF development cycle, while in Part II, we examine each of the development stages in more detail. Software tools have become crucial to the communication of a software development method. In effect, the tools encapsulate the method, in some instances to such an extent that the design method itself becomes of secondary importance. Tools can guide the developer to a lesser or greater extent. We have taken the view that there are already sufficient excellent tools available for the early analysis of an application provided it is already written as sequential code and not written directly as parallel code. There are also dangers in locking a development system into a toolset. For example, a software tool at the end of its lifecycle may no longer be supported whereas a tool at the beginning of its lifecycle may involve the developers in product Beta testing. Nevertheless, tool construction is important and this chapter examines the special requirements for tools to aid the development of PPF systems. Reference [11’7] is a more general study of software tools for parallel systems. Chapter 5 will consider the need for a development stage when the code exists in a purely sequential form whenever larger-scale applications are constructed. Sequential code can either be legacy code or it can be code written with subsequent parallelization in mind. If the latter enterprise is undertaken it is wise to have design rules ready for the programming team to avoid needless work when the code is parallelized. Most legacy code in the real-time 57
58
DEVELOPMENT
OF PPF APPLICATIONS
domain is in the C programming language as many devices (notably DSP chips) only have a C compiler available.
4.1
ANALYSIS
TOOLS
Analysis of larger parallel embedded systems may rely on prepackaged schemes such as the Yourdon dataflow method [134]. The dataflow approach is bottomup and avoids fixing the design prematurely. Dataflow is intended to approximate the way people see systems. The advantage to the designer is that the system might be applied to a sequential programming environment, a pseudoparallel or concurrent system, or a parallel environment. The raw dataflow system does not capture timing information, however, raising questions about its suitability for real-time systems. The PARET environment [257] for multicomputers has similarities with dataflow schemes. The parallel application is represented by a network of nodes connected by arcs. Tokens, representing data or control flow, pass between nodes. Buffers can store tokens. State transitions occur according to node output and input policy, which bears a resemblance to modeling by timed Petri-nets [258], usually applied to small-scale systems. The user can zoom in at successiveresolutions. The PARET system is suitable for a variety of purposes; examples given are a parallel simulator of MOS circuit timing, and a hypercuboid computer interconnect (a hypercube topology but with a cube of processors at each node rather than a single processor). The aim of the PPF development system has been to produce a machineneutral system description, which will reflect linguistically based thought processesin developing a design. Computer environments frequently model an aspect of the world. In the PPF toolkit it is important to present such concepts as ‘pipeline’, ‘data farm’, ‘flow’ and ‘hotspot’, which do not necessarily exist in other visualizers. ParaGraph [153] is a well-known example of a tool which aims at the widest generality. ParaGraph provides 25 displays interpreting the same event-trace data in different ways. In retrospect, ParaGraph’s displays lean overly towards the hypercubel, which at the time the tool was developed was regarded as the most likely general topology, in part because other topologies could be embedded within a hypercube [326]. By its nature, ParaGraph does not specifically support pipelined systems.
‘A two-dimensional hypercube is a square with processor nodes at each of the four vertices. A three-dimensional hypercube is formed by connecting two-dimensional hypercubes in such a way that corresponding vertices are connected by a link, with the result that each node has three links. Conflict-free routing can be achieved by routing along each dimension in turn. The most notable example of a hypercube topology is the early Connection Machine
WI .
TOOL
4.2
TOOL
In surveying
59
CHARACTERISTICS
CHARACTERISTICS existing tools, the following
user requirements
were identified:
Correctness checking. Soft real-time systems merely require verification of program behaviour. Safety-critical and hard real-time systems require something more than verification; either comprehensive traces or formal methods of proof should be considered. Performance debugging. identified. Processor
utilization
Cross-architectural
Slow downs,
is important comparisons
bottlenecks
or hold-ups
should be
when costing a solution. can also guide purchasing
decisions.
Prediction models can be used in conjunction with analyses of event traces to satisfy these requirements. A prediction model aids the identification of untoward behaviour which emerges from analysis of the event trace. Changing the communication and computation parameters within the prediction model is a method that has been successfully applied [316] in order to project performance to other machine types from timings at the basic-block level on a development machine. Should the tools be integrated? The term ‘integrated’ can be used in the sense that all tools have a similar ‘look-and-feel’. Integration can also imply that the output from one tool feeds into another, a toolset as opposed to [135], there are: EMU, which instruments a toolkit. In the MAD environment and monitors the application; ATEMPT, which provides performance analysis and error detection through visualization; and PARASIT, which simulates the application in order to predict race conditions. We decided to avoid the attempt to lock the user into a toolset and possibly lock ourselves into a restrictive toolset environment. On the other hand, the user is guided through a set of actions by the development methodology and the core prediction and analysis tools are integrated. The advantages and disadvantages of integrated toolsets are further discussed in [ill]. In a sense, the distinction lies between whether software design or system design is being undertaken. System design has a wider aspect as the software produced may be transferred to different hardware. However, just as the distinction between the development system and software development toolkit has become blurred, so has the distinction between system design and software design. The form of the user interface needs to be considered. A number of display types for parallel systems have been influential: l
The space-time diagram is common to a number of event-trace systems [395]. Its advantage may stem from the persistence of information displayed, allowing the mind to build up a pattern of activity.
60
4.3
DEVELOPMEIUT
OF PPF APPLKATIONS
l
The diagram-based display, such as SPV for the Paragon [173], is a way of showing process meters indicating parameters such as the instantaneous arrival and departure rates of messages, the activity status of a process, and link activity. A disadvantage of a diagram-based display may be confusion if large numbers of processes are involved, to counter which zooming is possible.
l
The state-change display is well suited to showing pipeline activity. In the visual programming tool HeNCE [33] the nodes of a graph change their shading according to activity in the associated process.
l
xpvm [124] has a run-time display system for networked computation using a space-time diagram. Bias introduced by the extra messages relaying the event trace make ‘on-the-fly’ displays unsuitable for realtime systems.
DEVELOPMENT
CYCLE
The PPF development cycle is shown in Fig. 4.1. Input to the cycle is a structured sequential program. The term structured is used in the technical sense of a program constructed by top-down analysis of its functionality [397]. As discussed in Chapter 5, the programming language ‘C’ remains the Zingua franca or common tongue of software for embedded RISCs and DSPs, and is entirely consonant with structured programming. Obviously, C++ is also employed now for construction of large-scale systems [207] for reasons of software reuse and as an object-oriented design framework. However, when a run of a program written in C~++ is profiled, Chapter 5, the same functional hierarchy is strongly apparent. Profiling tools become more necessary because the calling sequence is locked into the object structure. Existing sequential code is analyzed by existing run-time profilers. Examples of graphical displays from such a profiler can be found in Chapter 5. However, older profilers which produce tabular format timing information can in principle also be employed. When working with a large-scale software application in C++ then a class browser is an invaluable aid to partitioning as information hiding within an object is potentially at risk from an arbitrary partition. Transfer onto parallel hardware of sections or segments of sequential code may have unforeseen side-effects. It is always best to check the original sequential code with a memory debugger, which shows memory leaks, use of uninitiated variables, array boundary overruns and the like. The output from these analysis tools is a set of sequential code sections which can be incorporated into a template. The template is a high-level way of encapsulating the structure of the worker process. Unlike an object, a template is not a passive repository of the data and operations that can take place on the data. A template actively guides the usage of the software. In origin, PPF templates were programmers’ guides but at a cost in flexibility a graphi-
DEVELOPMENT
Feed-back cycle r-------------------------------------, II I0 8I
CYCLE
61
I 1II I
structured sequential programs
Fig. 4.1
PPF design cycle.
cal front end is being introduced. This makes a template resemble a software component [109] which only presents an interface to the user. Ideally, a parallel software component would only contain a parallel structure irrespective of granularity. There are also tentative ways of determining a necessary but sufficient set of operations that the component should support. However, the template represents the stage before that idealization. The design of PPF templates is further discussedin Chapter 7. Timing data from making test runs on the sequential code is also output from the analysis stage into the performance predictor tool. Library calls to time sections of code can be made on most processors and environments, though these differ considerably in accuracy. In fact, the calls can give a false assurance of accuracy and/or what is being timed. The Unix call gettimeof day times by secondsand microseconds yet the resolution of most workstation clocks is to the millisecond. Whether a clock records wall-clock time, processtime, system time or user processtime is also an issue. Reference [163] is a guide to the vagaries of benchmarking parallel machines which also considers timing in general. When a code section has been instrumented, the time within that section can be gathered as a mean or include the variance. For deterministic algorithms, where there are no branches then the variance will not be relevant. However, bear in mind that system noise can disturb deterministic processesto a lesser or greater extent [go]. Some algorithms are data-dependent and require a set of realistic test data to determine the long-term behaviour. The mean and variance, second-order statistics, can in principle serve to determine a statistical distribution for that behaviour. In practice, the distribution may be difficult to determine. However, there are still analytic methods for judging the impact on a complete pipeline.
62
DEVELOPMENT
OF PPF APPLKATIONS
The performance predictor works by simulation. Simulation can be supplemented by analytic methods, as discussed in Chapter 11. Because it is desirable to compare predicted with actual performance the simulation should set up a visual impression of activity within a pipeline segment which the designer can compare with recorded activity on the prototyping machine, using a similar display format. The display format of the simulator is deceptively simple: l
The PPF methodology restricts, in terms of the types of pipeline and the use of processor farms, the degrees of freedom in the parallel system development path;
l
Extraneous detail is avoided so that the mapping between prototype design and target system(s) is not prematurely fixed.
By alternating simulation and analytic predictions the performance of a complete pipeline can be built up in a piecewise fashion. A configuration file is output from the predictor tool. There is little standardization among the format files for parallel configurations. Therefore, a set of format drivers is provided. In addition, as configuration files merely provide a topology in the mathematical sense,a high-level description of the pipeline layout is also output. PPF templates are instrumented, ideally transparently to the user code. This allows output in the form of event-trace files to drive a performance analysis tool. The analysis tool mimics the graphical display for the predictor tool in order to make comparisons between the expected performance and the actual performance. Instrumenting a parallel system is not a trivial affair as no global clock exists. The problems become worse if the instrumentation is also used for debugging purposes, to detect race conditions for example. In this case, instrumentation and recording times critically may interfere with the accuracy of the data: the probe effect. Equally, when an event trace is visualized it shows a physical PPF with feedback routes and folded stages whereas the predictor tool shows a generalized PPF which is abstracted from the physical implementation. These issuesare discussedfurther in Chapter 6.
4.4
CONCLUSION
This short chapter has provided an overview of the PPF design cycle. Software tools are now considered an essential support to the design of a system. Careful thought should be given to the choice of tools, though it would be naive to think that there is a perfect solution for all facets of a system’s development. By starting development with sequential code, existing tools for uniprocessor systems can be employed. Performance estimation is an important issue for real-time systems so at the heart of the design cycle should lie tools for estimating the likely performance and checking that the specification
CONCLUSlON
63
has been met. Much of the structure of a PPF system has the potential to be boilerplated, by repeated application of software templates, and this both simplifies and focuses the design of the required software development tools.
Part
II
Analysis and Partitioning of Sequential Applications
5 Initial
Development of an Application
This chapter is concerned with the initial stage in development when a project is conceived, initiated, and the first steps towards partitioning are taken. As we explain, in PPF there is an emphasis on providing a separate stage of development built around sequential code. In other words, for the type of complex embedded applications which might require parallelization, we do not consider it a practical proposition to go directly to parallel code without first developing a sequential version of the algorithm. As PPF is also intended for legacy code, the form that sequential code takes is not overly prescribed, for example by eliminating unnecessary data dependencies. However, a minimum set of rules to aid the development of parallel code from sequential code could easily be extracted from a perusal of this chapter. The chapter also offers general development advice for parallelizing code.
5.1
CONFIDENCE
BUILDING
Before an embedded system involving significant capital outlay is embarked upon ‘for real’ there is period of confidence building. The function of the confidence building phase is to convince or persuade the project’s backers that the project is feasible, and that the stated performance is achievable. A project’s backers may variously be higher management within a business company, an outside governmental or institutional funding agency, or a venture capital organization. The implementors themselves will also need to edge towards a solution, as with any new endeavor the outcomes are by no means 67
68
INITIAL
DEVELOPMENT
OF AN APPLlCATlON
assured. Confidence building is at the heart of the ‘waterfall’ model [312, 3351 of the software life-cycle, in which clearly defined stages are passedthrough: requirement capture, specification, software design leading to implementation and testing. The ‘waterfall’ development process, though suitable for very large projects, can be rather ponderous, which is why exploratory programming or prototyping are preferred when time to market is critical. All methods of system analysis and development incorporate the idea of iteration, whereby the design is refined in the light of experience. Confidence can also be established by some tangible demonstration such as a small scale version of the intended system. The Marconi target-tracking parallel radar system [97] referred to in Chapter 1, Section A.1 consists of a set of pipelines each stage of which is a processor node of forty or more modular processors. The very first step in constructing this system of many hundreds of processors was to construct a single node. Before software was written the timings of the inner loops were found by reference to processor specifications. Subsequently, the performance could be timed by putting in delay loops with the perceived characteristics of the final, yet-to-be-written, software. Subsequently, software tools, such as Transim [149], took this idea further, producing a simulation environment in which inner loop timings or estimates could be inserted. Potentially, this approach avoids the problem of estimating performance before a parallel machine is available, as parallel structure is available in the simulator though the simulation itself is playedout sequentially. At the heart of Communicating Sequential Processes(CSP) [161] is the idea that parallel systems are in essencecompositions of sequential processes. Put another way, any parallel system can eventually be reduced to a set of sequential code segments. The Marconi real-time example highlights a difference between the software development path of many large-scale systems and that of soft, real-time systems, where timing guarantees at an early stage are especially important at an early stage. As a radar dish turns it receives a stream of reflected pulses which go through various signal-processing routines before the detection of moving targets. Failure to detect a particular target may not prevent the operation of the radar in the short-term but in the medium term would certainly soon be critical if the target were an aggressor. Developing (say) a database enquiry system for medical records has a lesser degree of real-time criticality and therefore the software functionality can first be ensured. One can conclude that confidence building in parallel systems is equally about establishing performance and functionality whereas in other domains functionality has a more dominant role. Establishing performance limits for PPF applications will be covered in Chapter 11. During the phase of anarchic development of parallel systems which occurred in the late eighties and nineties [88] it was unfortunate that many small-scale one-off solutions from research groups emerged but few large-scale commercial systems were built (the Marconi parallel radar system is an honorable exception). Often system analysis was neglected as there was little need
AUTOMA77C
AND
SEMI-AUTOMATIC
PARALLfLlZATlON
69
to coordinate work within large projects or to build-up confidence once initial backing had been secured. A consequence of this phase of stunted projects is that little thought was given as to how the development of parallel systems differed from that of sequential systems. There are many difficulties in the development of large-scale parallel systems. For example, a popular method of system development is reuse, whereby systems are constructed from a set of pre-existing components. The variety of rapidly evolving parallel architectures [302, 121, 162, 332, 328, 334, 921 and languages [276, 3841 inhibits reuse in parallel systems, when compared with the corresponding stability and slow evolution of conventional sequential processors and languages. One solution is to construct a set of parallel components that embody parallel structure but hide the implementation [60]. The solution adopted in PPF is to utilize existing sequential code as the raw material from which systems can be constructed, and also to provide a software template which embodies parallel structure in a general fashion. Given the historical record of parallelism, using a purely parallel solution with parallel algorithms and a parallel language, may be perceived by potential backers as a leap in the dark, justifiable only for small-scale systems where little is lost by failure. Using existing sequential code before parallelization means that confidence is already established by the fact that the code works. Timing sequential code segments is also a way of gaining confidence in the performance of the system. In fact, writing code in a constrained sequential environment can be viewed as a necessary preliminary step before parallelization. Subsequent changes can first be applied to the sequential version of the code to ensure the correct results still occur. The changes are then transferred to the parallel version where any failures can be attributed to the parallel implementation and not to the code itself. As an aside, it should be pointed out that there are reasons for the resilience of sequential programming that go beyond any possible advantages of the model. An essential task of any manager is to assign work tasks to individuals or teams, depending on the project size. However, in multimedia projects there is a clear divide between those software engineers who are algorithmic developers and those who are implementors. It is often difficult to divorce an algorithmic developer from the familiar, personal workstation environment. An implementor will however be more interested in the details of the technology than in the precise workings of an algorithm.
5.2
AUTOMATIC
AND
SEMI-AUTOMATIC
PARALLELIZATION
Given that a sequential coding stage in system development may well be needed, in what ways can the transition from this stage to the corresponding parallel partition be automated ? It would appear that automation is only possible for a limited range of problems; these do not currently include most
70
INITIAL
DEVELOPMENT
OF AN APPMATION
embedded applications, which typically have a complex algorithm and/or data structure. A complex system is one in which multiple algorithms are combined. The algorithms may each involve processing of dissimilar data structures. In contrast, a linear algebra algorithm will involve similar data structures throughout (usually matrices). The parallelization of a single linear algebra algorithm may take place in isolation as such algorithms often form part of code libraries. Automatic parallelization of sequential code for linear algebra can be attempted by data-parallel versions of Fortran [251]. Parallelizing compilers (which convert automatically from sequential code to parallel code) are successful in extracting loop-based parallelism for well-behaved languages like Fortran [281], but less successful where there are intricate data dependencies. In [5’7], it is argued that parallelizing compilers are unlikely to work in the general case because no information in the code tells the compiler how to schedule sub-tasks, how to map tasks with an appropriate granularity, and how to specify the distribution of a data-structure for a particular architecture. On the other hand, a parallel language may also suffer in practice from being tied to one class of parallel architecture: distributed (partitioned) memory, or shared memory. ’ The language Par [57] offers guidance to the compiler in the form of program annotations to direct the parallel implementation. In effect, annotations are an extension of compiler pragma directives. An early example of an annotated language is Kali [238]. The program itself captures the core parallel logic whereas the annotations can be changed according to circumstances. This approach may well work with numerical analysis algorithms, but may not be adequate to cope with the logistics of larger, multi-algorithm applications where any core parallel logic is often not apparent above the surrounding code detail. Annotations have also been taken up in High Performance Fortran (HPF), which was designed for portability. However, they do not directly provide a portable solution as different annotations will be needed for different machines. An alternative is to compile to an intermediate form (F-code) which may contain access invariants [331]. Again though, F-code is largely applicable to Fortran and as such to regular problems as found in linear algebra. Within the Fortran world, the problem that compilers assume worst-case data-dependency may be approached by eager or optimistic evaluation [24] and subsequent roll-back if necessary. Run-time scheduling of paralleliiation is also a feature of the Jade environment [307]. Jade detects static parallelism within ‘C’ programs and resolves data-dependencies during a run by means of supervisory software. Jade also employs code annotations. Unfortunately,
’ In theory, however, a language and the language extension, mented on a variety
one should distinguish between the programming model presented by machine model onto which it is mapped. The Linda programming though ostensibly aimed at shared-memory machines has been impleof machines [lo] including NOWs with a distributed memory model.
LANGUAGE
PROLlFERATlON
71
run-time parallelism mainly seemsto be fine-grained, and as such is unlikely to be of general use in embedded systems. While automatic parallelization may not be feasible, semi-automatic parallelization has more potential. A novel development is the construction of a tool which will aggregate granularity [388] for those parallel algorithms or parallelizations which are too fine-grained (presumably having originally been intended for a machine with a different compute/communicate ratio, as a result of moving from shared- to distributed- memory). Granularity detectors may emerge as a semi-automatic aid to parallelization. The Tag tool [102] is part of an ongoing effort in this direction based on much earlier research WI It *may also be possible at somefuture date to simulate the effect of different pipeline partitioning schemes. In [3] address tracing has been adapted in order to analyze potential communication patterns. An address-trace tool, DCompose,simulates the parallel behaviour of a sequential program. The sequential version is annotated with a possible method of data placement. The assembler code is instrumented around each data load or save. This is not a daunting problem on RISC microprocessors because of the absence of multiple addressing modes, since it is only the general pattern of data accesses that are of interest. The intercepting software calculates the processor which would store the data for a particular partitioning schemewere the application to run on a parallel machine. It is however unclear how the DComposemethod would adapt from monolithic algorithms working on one large decomposed data structure to algorithms which have multiple data structures accessedby a number of algorithms.
5.3
LANGUAGE
PROLIFERATION
The previous section discussedexperimental approaches to parallelizing code, often using new languages, or language variants that would not compile on existing compilers. Unfortunately, there are serious difficulties with the concept of ‘yet another computer language’ for embedded systems. ‘C’ compilers are still the ‘lowest common denominator’ or common factor across DSP and real-time RISC. Another compiler for any processor represents a significant development effort. As a more viable and limited alternative, the Parallel ‘C’ [l] approach (from 3L Ltd.) of introducing parallel constructs into ‘C’ by library calls has been successful for the transputer, the i860, the Texas Instruments C40, and the AMD SHARC. Java has had some support, for example in VxWorks [387], because of its popularity as an internet language. Many of the constructs of C++ have been employed which easesthe programmer training problem. Despite the similarities with C++, Java may be viewed as closer to a component-based language [169, 3441 than to an object-based language. For example, Java prefers references or interfaces rather than pointers. Automatic garbage col-
72
IIWTIAL
DEVELOPMENT
OF AN APPLlCATlON
lection nevertheless represents a barrier to Java as a real-time language as it introduces unpredictable delays. A number of measures such as provision of a Just-in-Time (JIT), or hotspot compiler have been made to improve the processing speed of the Java interpreter. 2 There is also interest in a parallel version of Java, see [47] from an issue devoted to this topic. Because of Java’s established momentum, there is already support for software development (such as Symantec Cafe and JBuilder), on a par with that available for the ‘C’ programming language. The Jini distributed systems layer [99] (also now used in VxWorks) and JavaSpaces [118], with implications for embedded systems, have also been added to the numerous existing application-specific software libraries. With the existing commitment to these languages, it seems unlikely that another language beyond ‘C’ and Java will now emerge in the embedded sphere.
5.4
SIZE OF APPLICATIONS
An inherent weakness of research is that realistically sized applications are often not investigated until late in a project. It may also be difficult to obtain or construct larger scale applications. Equally, the manpower available in a research project is usually quite limited. To address these points, the approach in developing PPF was to utilize existing application codes written by other software engineers whenever possible. All codes were written in ‘C’. Three initial applications were: A handwritten postal address recognition application, circa 4500 lines of code, written by computer vision researchers at the University of Essex (see Chapter 3); The Telenor (Norwegian Telecom) circa 7900 lines of code;
hybrid
video encoder,
H.263, with
MIT’s (Massachusetts Institute of Technology’s) ‘Eigenfaces’ face identification system, with circa 8700 lines of code. The number of lines of code in each of these applications approaches the limits of University attempts at parallelization, which is about 10,000 lines [268]. Commercial and financial systems are very much larger, up to lo6 lines of code, but it can be assumedthat for embedded systems these applications approach the correct scale of problem, particularly since embedded systems will usually run on direct or hard memory, with no virtual memory support.
2A JIT compiler compiles a method’s code just in time for its first use, whereas additionally a hotspot compiler introduces dynamic optimization of code such as function inlining [169]. Garbage collection is accelerated as well.
SEMI-AUTOMATIC
PARTlTlONING
73
Various versions of the postal address recognition application were parallelised over a lengthy period of time, as part of the PPF research and development program, so the time spent parallelizing this application is not representative3 The ‘Eigenfaces’ program took one man-month to parallelize, whereas the H.263 application took about three man-months. H.263 does not have a straightforward pipeline structure like the ‘Eigenfaces’ application. There are multiple feedback paths. Folding-back the pipeline could not be achieved in a convenient form as with the precursor encoder H.261 [87].
5.5
SEMI-AUTOMATIC
PARTlTlONING
Semi-automatic partitioning of sequential code can be achieved by a top-down profiling tool. The profiler will identify the principal parts of the algorithm in terms of functions. It is assumed that the functions represent meaningful groupings of the application’s activities. The dependencies between functions indicate where it may be possible to aggregate functions to form a computation process suitable for placement on a single worker processor. However, knowledge of data structures within an application is also needed to resolve dependencies. This is accomplished through familiarity with the algorithms involved and is confirmed by reference to the code, hence parallelization normally needs to be undertaken by a programmer who has a detailed understanding of the application algorithm, rather than being purely a parallel processing specialist. In Chapter 10, the speech recognition counter-example illustrates that an intimate knowledge of the data structures involved is essential, as although functions in one branch of the computation act independently of others, these functions also update a dominating global data-structure, the decoder network. Another purpose of profiling is to identify portions of code that take similar times. In the event of feedback, it may be possible to alternate between two sections of code in a particular stage of the PPF pipeline (refer to the H.261 encoder example in Chapter 8). The long-established profiling tool gprof [138] can be used to determine timings and a call sequence. For some types of code, especially recursive routines, there are doubts over the statistical sampling method employed by gprof [283]. Quantify [293], which works by object-code modification, has therefore been preferred for PPF development, and also provides extensive GUI support for interpreting profiling data. In Quantify, each basic block has a ‘door-step’ module attached which counts the number of entries to the block in the course of a run. The number of machine cycles for each block (less the cost of the entry code) is calculated at the point of object code
3However, percomputer
The final reported
port from a transputer-based in Section 3.4 took less than
machine to an i860-based one man-month .
Paramid
su-
74
/N/TlAL
DEVELOPMENT
OF AN APPLlCATlON
instrumentation .4. A further attraction of Quantify is that it will work with a multi-threaded application. Threads might be used to simulate parallel applications. An example of a call graph produced by Quantify for ‘Eigenfaces’ is given in Fig. 5.1.
Fig. 5.1 Call graph for the Eigenfaces application.
Profiling of sequential code indicates a static partition but does not take into account communication costs. If communication can be overlapped with computation then a static analysis is adequate. The same can be said if communication costs are proportionate throughout the proposed stagesof a PPF. After static analysis, the pipeline can be adjusted heuristically by altering the number of processors at each stage should the communication costs be disproportionate at a particular stage. For example, increasing the number of processorsmight also disproportionately increase the communication cost. In this eventuality, it may prove difficult to balance the pipeline. However, no such instances have been found so far and it is safe to say that such cases would be obvious at an early stage.
4Note that PPF does not require the timing accuracy that (say) might be necessary for improving a compiler or a random access hashing function as the static timings will inevitably be altered once parallelization has taken place
PORMVG
5.6
PORTING
CODE
75
CODE
Once a tentative partition of the code has been achieved the code can be decomposed. In fact, before this happens performance estimation will normally take place. However, the porting details are included below, before the discussion of performance estimation in Chapter 11, because porting code to a parallel platform is actually initially concerned with sequential code. The following steps are required according to [41]. The first set of steps is for sequential code: 1. Check the consistency of the code. 2. Understand the control and data structures. 3. Improve the code quality. 4. Gather runtime statistics. 5. Optimize the most time consuming parts. The second set of steps concerns the parallelization: 1. Choose an appropriate data decomposition. 2. Select loops for parallelization. 3. Modify the code according to the data decomposition. 4. Insert communication statements into the source code. 5. Test the parallel program on the target machine. 6. Profile the parallel execution. 7. Optimize/restructure
the parallel program.
With the ‘Eigenfaces’ application [llO] almost all these steps were taken. The exceptions were that only obvious algorithmic mistakes were corrected as they were met; and the sequential code was not manually optimized (though the features of an optimizing compiler were used to considerable effect). Extensive changes to code are unwise if that code is at an early stage of development, because of the difficulty of maintaining consistency. In fact, it is preferable to remain faithful to the original sequential version in all but performance. Our experience from parallelizing a range of applications has been that some characteristics of conventional sequential software development make the porting/parallelization task more onerous than it might otherwise be. The principal problem is that distributed-memory machines naturally require data messagesto be passedby value. However, in sequential code it is common
76
INITIAL
DEVELOPMENT
OF AN APPLICATION
practice to bundle all the parameters that may or may not be needed together into structures (the ‘C’ equivalent of a record data structure). An address pointer to one or more of these structures is passed to a function. Within the structure there will be further pointers and indeed chains of three pointers have been encountered in some examples. Unfortunately, programmers do not follow the advice of Ousterhout [266] and notate pointer variables with a suffix Ptr .5 Another bad programming habit (from the parallelization point of view) is to dynamically create a data-structure within a function, but free it elsewhere. One of three techniques might be tried to accomplish the decomposition of the code at function boundaries: 1. All calls by reference can be replaced by calls by value which in turn are replaced by messages at the point that the sequential program is partitioned. A problem with this approach, apart from the loss of efficiency in the remaining sequential sections, is that the unfamiliarity of the code leads to elusive errors. 2. A more successful method is to change only the type of reference at the points of partition. From the point-of-view of future modifications it would be sensible to pass the pass-by-value structures as one message. However, if the software has not originally been written with message-passing in mind then an overhead from copying into the message structure arises. 3. Sending separate messages for each data-structure may therefore be preferred. A large number of different types of message are then generated (over 40 in the ‘Eigenfaces’ application). Systematic organization of the messages avoids problems from varying message lengths. However, verbose processes are a difficulty when. later employing an event trace (Chapter 6). A verbose process is defined as a process that emits a large number of messages without necessarily having a large effect on the parallel logic. One verbose process can fill the visualizer display. If the event buffer needs to be flushed by any one process then the accuracy of the complete trace is compromised. However, this is a second-order problem that should be addressed by the event-tracer software rather than the application programmer. Which of the three approaches for coding the message interface is chosen is a mixture of personal preference, the application’s characteristics, and the perceived overheads.
5Though it is true that a pointer is easily identified at the point of declaration by the * notation, e.g. int * ip;, in the body of the code, pointers may occur without this notation. It is time-consuming and tedious to have to continually refer back to the declaration.
CHECKING
A DECOMPOSlT/OlV
77
The problems identified in porting sequential code to parallel code are easily remedied if it is known in advance that code will be parallelized. It is then a straightforward matter to avoid the difficulties in resolving pointer references by always passing function parameters by value at potential partitioning points within the software.
5.7
CHECKING
A DECOMPOSITION
Porting essentially involves dereferencing pointers whenever they are employed as parameters. When converting to arrays, errors may result due to overstepping array bounds. Purify [151] was helpful in detecting run-time errors of this type. Purify works by inserting extra instructions into the object code wherever there is a memory access instruction. The access is checked against a state table for every byte of heap memory. Clearly this will catch all access errors for dynamically allocated memory, including memory leaks. However, Purify does not detect array bound errors for static memory except when a read is made to uninitialized memory. When converting from big-endian processors (e.g. those from Sun) to little-endian processors (e.g. those from Inmos and Intel) errors may arise due to reversing the byte order. Unfortunately, if the access is to initialized memory one may still “get lucky with a wild pointer”, so Purify, though useful, is not an infallible method of detecting memory referencing errors. Figure 5.2 is an example of a Purify display. The figure shows an array bound overstep and a memory leak (artificially generated). Purify will also show the location of errors in the source code.
5.8
OPTIMIZING
COMPILERS
It has already been suggested that source code should not be changed except where essential as part of parallelization: if the code to be parallelized is still subject to change, then changes to the parallel code should go in lockstep with changes to the sequential version and not be in advance, otherwise the two versions will be difficult to reconcile. It is, however, possible to improve the performance of code without changing the source code by using an optimizing compiler for the target processor. Code developed for parallel systems is, in this respect, no different from code developed for sequential systems: in both cases the advice is to avoid premature optimization [44], which will slow down compilation. Any improvement in such a ubiquitous process as compilation is important in a production environment, though greatly improved processor speed of late has ameliorated the situation. If repeated testing is taking place and/or lengthy compilations are occurring then compilation switches can always be removed temporarily. The sequential version of the code is always the reference version as the sequential environment offers the necessary constraints and range of tools to enable correct working to be easily verified.
78
IN/T/AL
DEVELOPMENT
OF AN APPLICATION
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .: .. .. .. .. .. .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .>:. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~~~~~~~~~~~~~~.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
. : . : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . :. : . . . . . . . . . . . . . . . . . . . . . . . . . . . . :. . : . . . . . : . . . : . . . . . . . . .
j#
Finished @# Purify #j$ UMR:
......... ....................................................................................................................................................................................................... . . . . . . . . . . . . . . . . . . . . . . . . . .: . > : . : . : : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . ~ : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . ~ : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . ~ : . : . : . : . ~ : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . : . .: . .: . . . . . . . . .
pipe
t
3 errors,
0 leaked
bytes)
instrumented pipe (pid 1429 at Mon Flug 18 12~03~48 1997) Uninitialized memory read This is occurring while in: strcat [r-t1 ib,ol main Cpipe,main+ol start CcrtO+ol Reading 1 byte from Oxf7fff548 on the stack, Address Oxf7fff548 is 264 bytes below frame pointer in function main+
#j$l ZPR:
Zero
page
This is occurring memcpy
Pipe PiPC
main start
This is occurring slalgn Pipe pipe main start
read
while in: Crtl ib,ol Cpipeline+ol Crtl ib,ol [pipe-main,ol Lcrt0.03
while in: Clibc+so+l+91 [pipeline+01 Crtl ib,ol [pipe-main+01 CcrtO+ol
Fig. 5.2
A test run of Purify.
Once the code has reached the Alpha testing stage, then optimization can be considered. At this stage, a profiler will highlight the most costly parts of the code and in particular inner loops. This should be well-known already to developers of sequential code. Optimizing compilers can be set by level or sometimes by individual feature. Differing types of code will respond to different optimization techniques. Each section of sequential code intended as a single computation process on the in-house Paramid i860-based parallel machine was compiled by the Portland optimizing compiler [284]. This compiler has a large number of options which can be turned on in order to tune the performance. Broadly the categories of optimization are: local block optimization; global optimization across blocks; software pipelining (overlap of instructions) within a countable loop; vectorization and loop unrolling; and function inlining. The i860 [22, 1191, which is a RISC superscalar design (graphics, floating-point, adder, and multiplier units), was primarily designed for linear algebra and as such has features easily exploitable by an optimizing compiler: separarate data (128bit wide) and instruction (64-bit wide) caches, four-way vector processing, three-stage pipelines (and an external memory pipeline). The ‘Eigenfaces’ application did achieve significant timing improvements from the use of the optimizing compiler on the sequential parts of the routine. There was a 42% additional reduction in time for a single farm version
CONCLUSlON
79
running with 7 processors. Fifteen per cent of the improvement came from software pipelining. On the other hand, in the postcode recognition application, software pipelining only gained 0.08% advantage in timing. This should not be surprising as there are repeated calculations of KL transforms and Mahalonobis distances within the Eigenfaces application which in turn require calculation of variances within loops, and rely on a library of subroutines available from the well-known ‘Numerical Recipes in C’ [288]. In contrast, the postcode application has many sections of code characterized by repeated decisions in order to classify characters. Finally, once an implementation is fixed, further improvements in speed can be obtained by substituting hand-coded assembly language routines such as those available for the i860 from Kuck and Associates [198].
5.9
CONCLUSION
Historically, little attention has been paid to the development process for larger-scale embedded parallel systems. Given the need to maintain a version of the software on which algorithm updates can be developed and debugged and which can also be transferred to various parallel machines, it is difficult to see how to avoid an initial stage in which the application is coded for a sequential environment. The constrained sequential version of the code allows a range of existing development, debugging and performance profiling tools to be utilized. Existing tools for automatic parallelization can only realistically be applied to a narrow range of algorithms. Profilers are however of considerable value in exploring potential partitions, and memory-access checking tools can be useful for debugging parameter-passing across parallel partitions. If legacy code is to be decomposed then a strategy for identifying the contents of messagesis needed. However, if it is known at the outset that an application is to be parallelized then a set of ground rules for writing the initial sequential code can easily be specified, which will considerably simplify the process of parallel decomposition.
6 Graphical Simulation and Performance Analysis of PPFs Chapter 4 gave an overview of the development process (summarized in Fig. 4.1), which shows the various stages considered in this chapter. Chapter 5 considered the early development of an application. This chapter considers subsequent stages of the PPF development, and example performance, prediction and analysis tools (designed as part of our research and development of a PPF design methodology) are described. Prediction and analysis are linked because a similar graphical format is used in both the predictor and analyzer software tools. The input to the predictor tool is a set of timings, derived from test runs on the sequential code version of the software, whereas the input to the analyzer is a timed recording of communication events between the parallel processes making up the PPF. The predictor and analyzer tools are intended to be integrated with a templating tool (described in Chapter 7). Before a graphical format for a template tool was considered, programmers’ templates were produced for various parallel and distributed setups. Recent work has examined a Java RMI (Remote Method Invocation) version of the template. The integrated software toolkit is called (APTT) (Analysis, Prediction, Template Toolkit). The predictor tool is based upon a discrete event simulator [131]. While it is possible to simulate both synchronous and asynchronous pipelines, only asynchronous pipelines cannot be completely solved analytically. Determination of analytic results for asynchronous pipelines requires the use of waiting time distributions which are available for exponential distributions [63] but require queueing approximations for other distributions. A discrete-event simulator was constructed without difficulty as an alternative to analytic prediction. A 81
82
GRAPHICAL
SlMULATlON
AND
PERFORMANCE
ANALYSISOF
PPFS
simulation also enabled start-up and wind-down behaviour to be found, which analytic methods cannot provide.
6.1
SIMULATING
ASYNCHRONOUS
PIPELINES
Previous models of performance and scheduling [197] have supposedthat work tasks are divided into jobs. The number of jobs within a task can be varied to reach a benign scheduling regime, depending on the statistical nature of the job service-time distribution. There may also be savings in messagesize by grouping jobs into a logical task. In image processing for example, when spatial filtering of several image rows (jobs) is combined into one task, there is a reduction in border size. Conversely, where a task represents a physical unit, then splitting it into its constituent parts can reduce latency. This is because the latency of the subtasks can now be experienced in parallel. An example of a physical task is postcode recognition. Splitting the postcode into characters (jobs) reduces the postcode latency becausethe character recognition latencies can be played-out in parallel. At present, the task size in our simulator may vary between stages of the pipeline but not within a stage. Single jobs are passed between stages in a pipeline. A task is assembled from jobs held in an inter-stage buffer. The latency shown in a running display is the per-job pipeline traversal latency. Job latencies are grouped into their output tasks, enabling the spread of latencies to be seen. The per-task latency metric is found at the final stage by selecting the highest latency within the set of jobs making up a task. Ordering constraints when grouping jobs within the pipeline are not simulated as they are application dependent, but such degradation can be estimated by the use of order statistics (Chapter 11). For example, in the postcode example of Chapter 3 there is an output ordering constraint as the postcodes must leave the pipeline in the order they entered, but breaking the postcode into characters may cause one character requiring extra processing time to hold up others.
6.2
SIMULATION
IMPLEMENTATION
Our simulation tool was written in the JavaTM 1.1 [64] programming language (version 1.2 appeared towards the end of this work) for reasons of portability. Java enables the portable distribution of applications without revealing the source code through the intermediate medium of byte-code. Java comes with a comprehensive graphical library, though implementational weaknesseshave limited its usefulness. Using a somewhat slower semi-interpreted language with additional byte-code integrity checking in the virtual machine caused us to carefully review approaches to dynamic display. As mentioned in Section 5.3, improvements to Java’s speed are on-going including JIT compilers
S/MiJLAT/ON
/MPL EMENTATION
83
and now hot-spot compilers. It is also possible to use ‘final’ methods to aid the compiler to optimise, and to judiciously arrange when objects are instantiated. When verifying the simulation against analytical results, the simulation update order was chosen to suit the calculation algorithm. The simulation loop was subsequently modified to perform updates in the order that the display is updated. An array indexed by pipeline stage and worker process records the outstanding work left at each worker process. A further array records the latency to date experienced by each job. Advantage was taken of multi-dimensional arrays, each dimension of which could have a variable number of elements - a feature of Java. When a job passes to an inter-stage buffer the latency history is passed with it. Because inter-stage buffers can be unbounded they would normally be implemented as a linked list. However, Java avoids pointers ostensibly for security reasons and destructor methods are replaced by background garbage collection, preventing memory leakage. The utility vector class methods allow the storage of object references and hence dynamic data structures. On locating the object, its contents are unpacked. The capacity of the vector is covertly and automatically doubled when necessary. At each step of the simulation the global minimum remaining work time is located. All other work times are decremented on each worker process and similarly all jobs waiting in buffers have their latency incremented. If the global minimum is found on a worker processor at the output stage, the latency and throughput characteristics of the pipeline are updated on the display. Before updating, if bounded inter-stage buffering is set, a check is made to ensure that there are empty buffer slots at the next stage. If not, a new global minimum must be found, though the output stage will always remain unblocked. The simulator is implemented as a single thread, so as to allow the incorporation of other user threads at a future date. Figure 6.1 is a simplified snapshot of the simulation process. Jobs are grouped into tasks, which may differ in size between stages of the pipeline. Tasks being processed carry a cumulative latency. Similarly, jobs within interstage buffers accumulate latency, as do jobs waiting in local buffers (not shown in Fig. 6.1). Service times are selected from a specified distribution on a per-stage basis. The simulation update cycle consists of finding the global minimum time (after tie resolution) from among the worker service times. In Fig. 6.1, the minimum is two, which value is deducted from all service times and added to all waiting jobs, resulting in Fig. 6.2. Finished jobs are moved onto another stage or output.
84
GRAPHICAL
SlMULAT/ON
AND
PERFORMANCE
inter-stage job buffer
ANALYSlSOF
I
PPFS
I
input jobs a m ~:~:&)~:i:iil...... ::$:&g;;
furtherstages
bate h arrival
c
3
key:
0 6
worker with = remaining service time.
.‘..............,5..’ job with ~@$$ t .............. = accumulated latency.
Fig. 6.1
6.3
GRAPHICAL
Simplified
,
snapshot of PPF simulation.
REPRESENTATION
A graphical interface [287, 861 is the user’s view of a toolkit, and in terms of person hours of design effort has been the most expensive part of the APTT development. Our design aims to exploit familiar user interface paradigms for navigating data entry screens and utilizing simulation and trace tools in order to reduce the user’s learning time. The interface was written in Java, which enabled a trivial port between the Windows NT and UnixTM operating systems which would not have been possible with X-window software, except in the not widely used instances of X implementations under Windows NT. A problem with previous analysis visualization tools, such as ParaGraph [153], is that a highly animated display occurs, rather like a cartoon film. The user may find it difficult to establish a pattern. Moreover, in seeking generality, with 24 ways of presenting data, no structure to the ParaGraph tool’s usage was provided. An over-animated display also reinforces the sequentiality of the simulation whereas the pipeline in reality has both local and general parallelism.
GRAPHKAL
inter-stage job buffer
I
85
REPRESENTATION
I
further stages
active tasks
key:
0 6
=
worker with remaining service time.
:.:.:.:.:.:.:.:.:.:.:.: job with I$$@g = accumulated latencv.
Fig. 6.2
PPF simulation
after update.
Figure 6.3, showing a summary of statistics entered, is taken from the APTT data-entry ‘wizard’ which has a familiar look-and-feel to ease user adaptation. Figure 6.5 showsa snapshot of the predictor running a simulation of the postcode recognition application described in Chapter 3. The pipeline backplane occupies the main window with details of the stage activity such as buffer and processor usage available from subsidiary windows. Processor activity is shown using color through analogy with stop/go displays. Again using the semantic associations of color, the communication arrows change color from black, through red to white to highlight communication ‘hotspots’. Provided the shades range in tone then this type of display is suitable for monochrome as well as color displays. The arrows also widen and contract, which is a format well-known in static displays [357]. Mean bandwidth, rather than instantaneous bandwidth is displayed, so that the rate of display change is smoothed out allowing the viewer to establish a pattern. The color scaling is adjustable to center on and bracket critical data rates as the variation across the full bandwidth range might otherwise be too low to show up; see Fig 6.4. Latency is also indicated in a persistent display. Jobs are marked off at task boundaries, with the task latency determined by the slowest job. Though persistent displays convey more information, they need to be balanced with
n
w E 0”
GRAPHICAL
87
REPRESENTATION
Also included in Fig. 6.5 are a couple of pop-up windows (activated by double-clicking on the farmer icons) which display the activity of individual farms. The pop-up windows themselves have further pop-up capability (not shown) which gives the number of jobs processed and the activity level of each worker process. In general, qualitative information is given priority but quantitative information is always available. Figure 6.6 shows the post-mortem analyzer window (used for reviewing actual performance after an instrumented run), with the postcode recognition application trace running, and the configuration set-up from an intermediary format file. As instrumentation is inserted transparently to the application the display does not try to infer performance statistics other than run-times.
..._ .___.__...._._....
Ldency)Job
Display
...-----..-.-.-------.-
Simulation
1 ! Min.
p----y
iMax.
/-i-T--i
i Mean.
jo81
control:
Sknulation
i Std. Dev: ‘..................................2El
---Simulation : @
Fig. 6.5
h bunter
APTT
Format
c
predictor
In Clock
lime: Format
window.
--.
speed:
Percentage
Act-:
88
GRAPHiCAL
i. ..__.___....__..._.____ $armr
SIMULATION
to Worker
Comunicq&n:
AND
PERFORMANCE
. ..__._......_._._. _._._
. . . . . ..__._.___...
ANALYSISOF
_ ._.._._....._.
In Cou-der Formal
_ _________.
.
..__... I
______._._...........___.____ I
I
I I
I I
500
550
800
. .. . . . . . . .
650
700
I I
I I
. :
750
800
;
panel:
@ h Clock Format
._._._...._...__........
Time:
_ _._._._..
_ .__.__._
_ .___ _
7
&f$M panel; .......-...............-............. i
i”“““..“‘~~......................
i
Time
PPFS
i?.................... ,..................................................................,....,..........................................................................,...................~.......................,...~.......... ... .. . ..ii~:: ~;.~.~;~~~.~.~.~.~.~.~.~.~.~.~~~~~~.~.~.~.~.~.~.~.~.~.~~ “.“‘.......‘~. ..........~~~~‘;..” p-vqmss~~~~~~\~. .$P;:5 a~~~~~.~\~~~~~~~~~~~~~~. \\\\\\\\\\B ~,:z ~~~~i~~i~.~“.‘.i~,~~~~~,~i~Xi,~~~;;~~~ .~~~i,~~~~;~~~~,~~~~,~~~~~~i~~~
~~~~~~~~~~~~~~:~:~:~~~~~~~~~:~::~:~~~:::~:::::::::::::~~:~:::~:~:::::::::~::::~::~~~::::::::::::::::::::::::::::::::::::~:::~:: :~:~.:.~:~~~:.:::::,:::.:.:.:.:.:2.:~:.:.:.:.:.:::.:::.:.:.:::::::::::::.:.:.:.:.:.:.:.:.~:.:.:.:.~:.:.~~:.:.:.~~~:.:.:.~~:.:.:.:.~:.:.:.: .:.:.:.:.:.:.:.:.:.:.:.:‘.:.:.:.:.:,:.:.:.:.:.:.:.:.~:.:.:.~~~:.~ :i~.i:i::i:i:~:~~:~~:~~:::.~~:.~:::~.:.:.~.:.:.:.:.:.::~:~.:::~.~::.~:~~:~~:~:~:~:~:~~:~:~:~~:~:~~~~~:~~:~:~~~~~:~~:~~~:~~~~:~~:~:~:~:~~:~:~:~:~:~:~~:~:~:~:~: \...: .::::~u:::::::::::i::::~:~:~:~:~:~:.:~:::~:::~:::::::.:.:.:~:::::~::::::::::::::::::::::::~:::~::::::::::::~~:::~::~:::~~~::~::::::::~:::::::~~:~:::::::::::::::::::::~:::::~:~~~: . .... . . . . . . :...:...:.:...:....................................:.:.:...:.:...:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.~:.:.:.:.:.:.:.~:.:,:.:.:.:.:.:.:.:.:.:.:.~~:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.: t : ........................:,:.:.:,: .. . , . .,.................................~..................................................................................................................... .... . . . . . . ., . . . . . . . .. . . . I . . . . . . . . .. . . . . . . ._,.,............ . .. . . _..,..., . . . ._............~.........,,~........~.. , . . . . . . ..: ~..r..,...,...,.......~.~.~.~.~.,.,.~.~.~.~.~.,.,.,.~.,.~.~.~.,.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~.~,~.~.~.~.~.~.~.~.~.,. ............................ .................‘............................................ .. ..‘... .. 5; .‘. ... .. ,L .,. .. .,. .,. .I 1:;
fig. 6.6
6.4
DlSPLAY
APTT
analyzer
window.
FEATURES
Animation using individual tokens for each messagemakes it difficult to distinguish between levels of activity, since the display is not persistent: after the passageof a token, it reverts to its previous state. The use of color in these types of display was mentioned in Section 6.3, and has been found to give a clearer indication of overall average activity levels. Because the passing of just one messageis normally not enough to change the arc color state, screen flicker is reduced. The end result is a slowly changing display, which as desired establishesa pattern of activity in the user’s mind becausethe display is persistent. The most difficult aspects of using a graduated color display are arranging step size and choice of color, and conveying when an arc’s com-
CROSS-ARCHlTECTURAL
COMPARISON
89
munication bandwidth has been saturated. Another indicator can be used to show saturation. The worker and farmer states are also indicated by color, either active, idle, or blocked through full buffers. The internal state of any worker is accessed by a pop--up window. However, notice that true pop-ups are not part of the Java Abstract Window Toolkit (AWT)l[123]. Arrangement of graphical objects on a display panel is timeconsuming, though to maintain portability object placement should be relative. The grid-bag layout was found to be the most convenient pre-supplied format. The tool was tested on a UnixTM-based workstation as well as a PC to confirm portability. Features of the display (Fig. 6.7) include: a Fine control of each stage’s communication parameters and work distribution; l
Zoom windowing on individual farms;
l
Communication ‘hotspot’ indication through arc color and size;
l
Color state change of farmer and worker activity (busy, idle and blocked);
l
Access to individual idling times and work history;
l
Inter-stage and local buffering monitoring;
l
Running indication of simulation time and performance metrics;
l
Controls over simulation display speed and state;
0 Selection of computation rate and interconnect bandwidth scaling (relative to a base setting); l
6.5
Help through WWW pages.
CROSS-ARCHITECTURAL
COMPARISON
To allow the performance within APTT on one machine to be extrapolated to another we sought a simple but widely recognized characterization. A twoparameter model of performance has now been applied to a variety of parallel architectures [163], though not apparently previously in a predictor tool. For example, in Fig. 6.8, which is a log-log plot, the Paramid reaches half its maximum bandwidth with messagesof about 60 bytes (first parameter, established IThe Java AWT uses the peer graphical components of the underlying operating system at some loss in efficiency. Subsequently, Swing Components [374], which are written purely in Java, have been introduced as a longer term solution to graphics programming in Java.
90
GRAPH/CAL
SfMUtAT~ON
AND
ANALYSISOF
PPFS
:........ ....
;; :i
PERFORMANCE
P!eese
enter
tfw requjfetd
nutM8rs
be(ow...
to ba
complete&
Parameters
: ,.........................-.....................................-...
p-EJ
>; Nunherdptpethnzslages: :. . (; wnber of jobs
: i
pti-
iNumber /Data
i: B&fertype: .. i input* .. : .. .
c
Unlimited
@
LimIted
Lknit:
110
Of
size
a$SlQneU for each
WOrkBr
featchnti
;>:...v............ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..‘.....~.....‘.....‘...‘.........’.............. : . . . , . . . . . y1 . . . .>.y.q 3 ~~~~~~~~~~~~~~~~~~~~~~~~~~ :iti . ”~~~~~~~~;~~~i ~i~~~~~,~ jiii‘~~iitti~~~~:~:~~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~:~~:~:~:~:~:~:~:~~:~~~:~~~~~: .,., ,., ,., ,., . . : :..:.: :.:.:.:.:.~:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.:.~:.:.:.:.~:.:.:.:.:.~:.: i. I:
Pipeline
processes:
job rate
7
;. :; ,
* . .. .. . ,.
j Number or JobsIn a work-task:
I’
;Computat~on
fy-7 :: Mean ............ ; m ; i Standard
rate
! Scheduling regime . . . .. . . . . .
Stege
r................-.......--..................................-.-.-.---.-..... : : : ’ m i i Enlty memod. @iEzjijs p----T i :i : Job dlstnbubon function Ip---: i i . . . . . . . . . . .; Lambda 13
: i Communication ,
for
_______..___.___..._..____..................:
of distribution
function;
devlatlon’
17
_:
Ii
. .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . . . .. . .
i:?..........................................................................., :i~‘ A‘ :ic .hS&Si&Wi&ihW~\hi\ B$$@zi%a ~#&p.x’:‘::: ~~~ .. .
,............................ ! @.
Fig. 6.7
h Comier
m-n Famed
Screen shot of the simulation
c
Time: In Clcck
. . . . . . . . . . . .. .. . . . . . . . . . . . . . .i
Formd
predictor
Time,
tool.
by linear regression) before reaching steady state (second parameter). In this case, the user need only know the messagelength and the target processor to project results. Measurements on an individual Paramid processor, an 2360, showed that a two parameter characterization might be insufficient for computation as there was dependency on the computation kernel being performed, with additional cache effects evident. Figure 6.9, showing results for four out of seventeen test kernels at full compiler optimization, indicates two linear phasesfor some kernels where the vector length being computed stays within and steps outside the cache. However, it is not a difficult matter to store in a look-up-table the results for each machine and for each kernel. The user then selects a kernel, vector size, and processor to enable the performance tool to give a first-order approximation by means of scaling the computation times. This is likely to be more helpful for regular computations such as orthogonal transforms. An alternative characterization is to use the computational intensity of the code, f, in units of flops/memory reference. Table 6.1 records steadystate performance (which is well below theoretically optimal performance), rg and T: being respectively in-cache and out-of-cache performance in units
CROSS-ARCHlTECTURAL
COMPARISON
91
of Mflop/s2 The settings for compiler optimization level three show a reverse trend to the expected increase in performance as intensity increases; compare level two in Table 6.1. However, we use the higher figures in order to make a fair comparison between the two processors.3 Table 6. I
f raCi ra!oc
1 25.6 18.1
2 18.3 16.1
Paramid 4 15.9 15.7
Computational 5 15.6 14.8
6 15.4 14.7
Performance 8 15.1 14.9
9 13.2 15.0
10 13.3 13.2
10
Fig. 6.8
Point-to-point
communication
performance
for the Paramid.
Applying the out-of-cache computational intensity test (level three setting for the Paramid), a Dee Alpha (21064 at 175 MHz) server was found to scale over the i860 by a factor of 3.0 for f = 5 with a -fast compiler setting. As this is a load-dependent measurement, the arithmetic mean of five selected results was taken. Table 6.2 records the projected timings if 21064s
2The out-of-cache measurements arise by using vector lengths designed to exceed the cache size, and by causing a cache flush between tests through repeatedly accessing a large array in random fashion. 3Note that at f = 5 out-of-cache performance is similar for both compiler options.
92
GRAPH/CAL
SlMULATlON
I
AND
PEt?FORMANCE
ANALYSISOF
PPFS
I
0.6
0.5
3 -5 E F
0.4
0.3
0.2
0.1
0
Fig. 6.9
100
200
300
400 Vector
Selected computation
500 length
600 (bytes)
performance
700
800
900
1000
for the Paramid.
were to be substituted for i86Os, otherwise keeping the system the same.4 The longer out-of-cache test figures were chosen because the lower resolution clock would otherwise affect the accuracy5 though in-cache timings indicated a larger scaling particularly for higher values of f, indicating an efficient memory hierarchy. Low-resolution software clocks may be a deterrent to the use of a processor in some hard real-time system, though probably not for the soft real-time systems considered here. Spatial filtering is an example of an image processing operation commonly performed with integer operations, whereas benchmarking kernels, being derived from the numerical analysis community, usually employ floating-point operations. There would therefore also appear to be a need for a set of agreed kernels specifically for image-processing and other integer/fixed-point operations, which are frequently required in embedded applications.
4This is not a practical possibility as the choice of processor and coprocessor is dictated by cost and compatibility, the i860 and transputer both being little-endian [59](the byte ordering is the same to allow exchange of complex data types, in particular floating-point numbers). 5 Clock resolution was N 0.01 s on the Dee Alphas as opposed to N 0.001 s on the Paramid, mean timing error ~l16.1%.
CONCLUSION
93
Table 6.2 Simulated Results for a Variety of Pipelines Dee Alpha (21064):
Paramid:
Run-time
Pipeline Worker Ratio
0S
3:2:1 2:3:1 4:3:1 3:4:1 3:3:2 3~412 4:4:2 2:5:1
6.6
35.1 27.6 24.3 23.9 23.5 18.6 17.7 27.3
Throughput
Run-time
Throughput
pcodes/s
0S
pcode/s
8.6
11.9 9.4 8.1 8.3 8.0 6.3 6.0
23.3 29.8 34.5 33.3 34.7 43.9 46.3 30.0
11.0
12.4 12.6 12.8 16.1 17.0 11.0
9.1
CONCLUSION
Tool-centric system design and development is well established. The most important part of tool design is the human--computer interface, which should present an easily assimilable model of the system’s behaviour. For this reason, considerable attention was paid to PPF graphical representation, which has the inherent advantage of presenting a single consistent model for all applications. Representing parallelism on a serial machine is difficult. The APTT toolkit explores the use of color for this purpose, presented via the Java portable graphical environment. This enables a single software toolkit to be used both in the Unix and Windows environments. PPF pipelines should also be portable across different processor types, and for this reason a simple, two parameter model of cross-architectural performance comparison has been utilized. The current research implementation of APTT is available at http : //esewww . essex. ac .uk/research/vasa/pstespa/aptt/.6 A description of the PSTESTPA project and the APTT software can also be reached fromhttp://esewww.essex.ac.uk/research/vasa/pstespa/index.html.
of a research project intended to investigate ideas 6Note that this softwa re is the outcome rather than to produce commercial strength software, and is made available for the benefit of the community. No guarantees can be given as to its performance.
7 Template-based Implementation The leitmotiv or driving aim of PPF design is to introduce genericity into the creation of parallel systems. Given this aim it is not surprising that ways of automating PPF implementations have been explored. A high-level template for data farms seemed an obvious way of doing this as it is relatively simple to link data-farm templates together to form a pipeline. The concept has been tested by implementing a template with the same functionality on several typical platforms. There are ideally two versions of the template: the first (parallel logic) is employed to gain confidence that the transition to a parallel implementation from the sequential code has worked; and the second (performance tuning) is instrumented (allowing timings to be made) in order to check that the desired performance goals can be reached. The reader should refer back to Fig. 4.1 to see how this stage fits into the PPF design cycle. Instrumentation perturbs a parallel system, potentially disguising data races adding overheads. It is also not easy to instrument a system without a global clock, which aspect is discussed in Chapter 12. A number of performancetuning templates might be needed in the course of time as and when a software pipeline is transferred to new target hardware. Templates already crop up in various related settings. Reference [60] introduced algorithmic skeletons which are a high-level template written in a functional language. The skeleton provides a parallel control structure but hides implementational detail from the programmer. A model for calculating the cost of the parallelization is provided. A number of similar structured approaches to parallel programming exist; for a comparative review refer to [329]. Coincidentally closest to the PPF approach, in the sense that farms and pipelines occur among the skeletons, is the Pisa Parallel Programming Lan95
96
TEMPLATE-BASED
iMPLEMENTATlON
guage, for example in [366]. The categorical data type (CDT) framework [329] for list programming is a related higher-level model which steps further back from the control structures necessary for a particular parallel architecture, and being polymorphic, is also without a preferred granularity. An attraction in principle of the skeleton/CDT approach is a formal and more complete software development scheme. More generally, the software component is a user-level variant of the programmer’s template. Like the template, the software component encapsulates dynamic behavior, and is not passive as is an object in object-oriented design [239] or in an object-oriented languages. The template is, therefore, at an equivalent level to the JavaBean or DCOM component [195] but with an informal interface, being available in source code form. A template implementation need not reproduce every feature of the design and can be built on existing software facilities, thus easing the implementational burden. Templates are used through a text editor in the manner of the Linda program builder [9]. The programmer can slot in sequential code sections, and form messages,provided the message-passingstructure is preserved. Other parts of the structure are transparent to the programmer, such as messagebuffering, and event-trace instrumentation.
7.1
TEMPLATE
DESIGN PRINCIPLES
The abstract design of the data-farm template was motivated by engineering utility. Communicating Sequential Processes (CSP) [161] was selected as a model of parallelism, in part because it has been successfully disseminated amongst the programming community, which in itself is a practical consideration. CSP presents a static process structure, that is there is no need to support dynamic process creation. A common characteristic of embedded applications is that the overall process structure is known in advance. Communication between two processesis solely via a channel causing a synchronous rendemous between sender and receiver. Otherwise processescan be scheduled in an arbitrary interleaving, though CSP provides a process algebra which in principle can establish correctness. CSP’s process algebra implies two important features from the efficiency standpoint: low-overhead context switching by means of multi-threading; and the ability to alternate responsesin a non-deterministic fashion. For easeof programming, between threads on the same or different processesshould be transparent and symmetric. These aims were also engendered in the transputer design and associated programming language, occam. However, the intention of our template design was not to emulate the transputer virtual machine, as in [271], but to incorporate the model in a looser fashion, relaxing non-critical features, and adding new features to enable smooth operation of the data farm.
TEMPLATE
DESIGN
PRlNClPLES
97
In CSP, channels are a means by which the normal semantics of a programming language may be extended in a seamlessway to include communication between processes. In [158], the absenceof a channel from programming languages is viewed as an historical accident due to memory costs. Channels form an implicit name space, without the need for a name-server. In a number of implementations of CSP there are no compiler checks to prevent a programmer writing to both ends of a CSP channel. Use of a template explicitly designs out this possibility. There is also a problem of excessive ‘plumbing’ inherent in the CSP channel, which results in the need for the programmer to keep a check on a large number of channels and ensure that messagescorrespond. Again, a template alleviates this problem. CSP, as implemented in occam2, is not sufficient for data-intensive applications such as low-level image processing, as excessive memory-to-memory data movements may be needed between threads. Unfortunately, on recent hardware, improvements in memory accesssignificantly lag, and may obviate, gains in processor speed. An indication of the problem is that the following techniques are all aimed at ameliorating memory latency: multiple caches; interleaved memory; and decoupled architectures. Therefore, shared memory was added to our template design, while it is not present in the CSP model. Support for shared channels has also been added in occam3 [29], originally intended for the T9000 series transputer. Similarly, the need to relax the occam specification has been recognized in [379], where semaphores, resources, events, and buckets are alternative synchronization mechanisms to the channel. In our template design, counting semaphores have several advantages as a means of controlling accessto shared memory. In PPF-style applications, semaphores are not needed extensively so that the danger of unforeseen interactions from disparate parts of the program is not present. Access to a critical region is not denied by a semaphore if data will not be compromised. An implementation of semaphoresrequires one process queue, a counter and a locking mechanism. The monitor construct was not included for a logical reason: it allows only one active call at any one time; and for a practical reason: its operation may be hidden from the programmer [382]. Other contention accessprimitives, for example the serializer [157], though convenient for the programmer were not considered suitable as resources are used inefficiently. CSP does not include complex communication structures. An asynchronous multicast from the farmer process to its worker processes was however deemed necessary in our template design to reduce messagetraffic. The multicast can also act as a means of synchronization for computational phases as well as physical reconfigurations. The multicast does not initiate any reply messages,thereby restricting circular messagepaths. Care was taken that normal communication could not overtake multicast communication, as a multicast will often contain start-up parameters. Message records were added as a useful structuring device, the equivalent of occam’sprotocols. To enable reuse, the communication structure was made
98
TEMPLATE-BASED
IMPLEMENTATlON
transparent to the type of application messages.A tag messageprecedes each data messagegiving the length of the messagefor intermediate buffers and its type for the application code. For soft real-time applications, two priority, pre-emptive context switching is sufficient but necessary. In the data farm, the higher priority is needed to respond to communication events if it is possible to provide an asynchronous response. Once the communication event has been serviced the responding thread deschedules. As a base-level facility, implementable on most platforms, round-robin context switching was also supported within the template. Scheduling of the ready queue is by a FIFO mechanism. As two levels of priority and a FIFO queueing policy are not sufficient for hard real-time applications, [367] describes an alternative CSP-based real-time kernel. Round-robin scheduling may also be viewed [216] as unsuitable for such applications, as it reduces response time. If there are many potential inputs, alternation may be a hindrance because of the need to monitor all the inputs [386]. However, for embedded applications in the PPF pattern the number of inputs was not expected to become large enough to make necessary a tree of multiplexed requests, and unlike hard real-time systems, deterministic response was not required. The datafarm paradigm is deadlock-free [378], thus avoiding the principle disadvantage of non-determinism. Buffers are employed at the user process level to mask communication latency and to increase bandwidth. The buffers will normally be transparent to the application programmer. Input buffers reduce the time spent waiting for work and output buffers smooth out accessto the return channel. Ideally, a one-slot local buffer is enough to mask communication but in practice a few more slots were needed because of variance in task computation time and communication hold-ups. CSP’s synchronous communication was retained. However, buffers act as agents [244] for the application which make it appear to the application that there is an asynchronous send and a blocking receive. Additional communication structure is provided to enable data-farm template instantiations to be grouped in a pipeline, with options for I/O if the data-farm in question is a terminal stage. The same buffering module is employed between pipeline stages but more slots are normally necessary to smooth flow between the stages (than for local buffers). A similar buffered pipeline design methodology has already been developed in [214]. A method of predicting the number of buffer slots for local- and inter-stage buffering is discussedin Chapter 11. Additional data-structures such as a linked list may be needed if arriving messagedata needs to be reordered before passing to the data farm. Demand-based data farming within the template is, in most cases, a way of scheduling work with limited loss of efficiency. At start-up time, a static scheduling phase is needed to fill buffers. Indeed, for constant task computation times, the time to fill all buffers should exceed single task computation time.
MPL
EMENTATlON
CHOICES
99
Instrumentation, recording communication events, is a built-in feature of the template. Experience [303] shows that instrumentation is difficult to include at a later stage and that a static design will need to be tuned after an initial implementation. In different circumstances, instrumentation has been included in a number of environments such as Jade [307]. Correct termination of the data-farm template is necessary for both the collection of outstanding results and the gathering in of trace files. It was anticipated that the farm might need to be reconfigured if the workload altered during the course of a run. On termination, the data farmer employs a sink process, which is broadly in line with the methods discussedin [377].
7.2
IMPLEMENTATION
CHOICES
Implementation of the design, in an object-oriented sense,is a processof establishing idioms, that is low-level features not present in the underlying software that are desirable. At first sight, existing communication harnessesappear to be a natural way of implementing a data-farm template in a distributed and/or parallel environment. The de facto standard for such message-passingcommunication harnessesis PVM [124] whereas MPI [143] is the de @re standard, and continues to be developed as MPI-2 [144]. However, message-passing[21] is different in kind from CSP, being asynchronous, and moreover starts with the pragmatic premise that a wide range of facilities is preferable to a tightly constrained communication model. Reference [125] is a comparison between PVM and MPI, where PVM’s support for heterogeneous processors within the virtual machine, and fault-tolerant features are pointed out. MPI-2 has introduced coordination of parallel I/O ( on Unix-like systems) and remote memory access (through memory windows). As PVM has an underlying dynamic model of parallelism, not static as in CSP, daemonsare also necessary to spawn additional tasks and to act as name servers. Where user-level dazmon processesact as communication intermediaries a performance burden arisesfrom the extra messagingneeded to communicate between user application and daemon. Many embedded applications simply cannot support this extra software superstructure. A number of features of PVM militate against implementing the design model outlined in Section 7.1. PVM does not support internal threads as there is just one process per PVM task. Therefore, a PVM task is reliant on probes if non-blocking communication is to occur. PVM lacks CSP’s nondeterministic operator and has no support for internal concurrency. PVM has a restricted set of message-passingprimitives, but in version 3.3 a system of buffers involving memory-to-memory copying restricts performance, though this may be remedied. Broadcasts in PVM 3.3 are not true broadcasts but one-to-many transmissions, necessary becausethe generality of PVM must accommodate networks without true broadcast capabilities. Different versions of PVM may exist on target machines (vendor implementations rather than Oak
100
TEMPLATE-BASED
MPL
EMEAiTATiON
Ridge implementations) for compatibility reasons. For example, the version of PVM available for the Paramid machine used in many of the examples in this book is restricted to a host/worker configuration. As all communication is routed over a SCSI link performance is limited. MPI has avoided daemonsor servers in its design. Instead, groups of processescoordinate within the context of a communicator. MPI-1 has a static model of parallelism whereas MPI-2 as part of a convergence with PVM has introduced dynamic process creation, but again through the communicator mechanism. Therefore, MPI is most aptly described as semi-dynamic. Obviously members of a group still have to generate traffic to coordinate among themselves. MPI is thread-safe but there is no support for internal thread creation in either version. Other features of MPI make the template design model difficult to implement. The message-passingstandard, MPI [143] does not supply a nondeterministic operator. In MPI, multicast is available but by way of its semidynamic process groups. ’ MPI has a proliferation of communication primitives that can lead to confusion. Whatever the advantages in portability, it may be unclear which message-passingmodes are efficiently implemented on the target machine. PETsc [26] is a remedy to this diversity for numerical software libraries. MPI’s derived datatypes, intended to improve performance becausethey avoid copies out of user space, are too low level for many tastes. A real-time version of the MPI specification [250] is in the process of addressing performance concerns. Given the limitations of PVM and MPI, it may be preferable to examine what native facilities are available to implement the main features of a datafarm template efficiently. In particular, a customized implementation gives the option to use a true broadcast if the LAN supports that function.
7.3
PARALLEL LOGIC IMPLEMENTATION
One of the template implementations discussedin this chapter was on workstations running SunOS 4.1. On Unix systems, the cost of context switching for a heavyweight process in a worst-case scenario might include swapping the user context from disc and cache flushing. Threads (lightweight processes)are a way of reducing the responsetime in either interactive or real-time settings. Communication can either be by means of a virtual circuit or by datagrams. The socket is an abstraction through which the programmer can interact with the networking software, typically by binding the socket to a source and destination address, by establishing a connection when a circuit is required, and by sending messagesvia the designated socket. Remote procedure call (RPC) was not chosen as a basis for the implementation because of the known over-
‘PVM
supports group co mmunication
through a further group manager daemon.
TARGET
MACHINE
MPLEMENTATlON
101
heads, which in [40] were already shown to be an order of magnitude above a procedure call on the same machine. On the SunOS 4.1 o.s., the socket application programming interface (API) [342], included from BSD Unix, was combined with lightweight processes (LWP) or user-level threads. 2 The result made possible implementation of most of the required features of the data farm. The BSD version of Unix implements the socket API directly in O.S. kernel space. The main weaknessof the original SunOS thread system is that all threads, and indeed all processes, share the one kernel instance. Therefore, it was necessary to employ asynchronous communication to ensure that a LWP does not prevent a context switch by blocking on a communication call. However, asynchronous communication is reliant on signal-handling which in standard Unix implementations occurs as a result of a context switch internal to the process.
7.4
TARGET
MACHINE
IMPLEMENTATION
A template was also implemented for the Paramid machine. From the user perspective, the Paramid appears as a multi-transputer (each with attached i860 accelerator) workstation application co-processor, onto which jobs are allotted on a first-come-first-served basis by a host-based scheduler (a Sun workstation). Interprocessor communication is effected in the first instance by the 860 interrupting the transputer (via the transputer event pin) to signal a request. The transputer inspects a common memory area in order to service the request, releasing a software lock after fulfilling the request. In Inmos parallel ‘C’ [172] for the transputer there is a set of thread library calls. Interaction with the hardware communication-link engines from within a thread is well defined on the transputer and posed no special problems. There is a choice of point-to-point physical channels or virtual channels. The virtual channel system (VCS) [78] enables direct global communication at a small cost from link sentinel support software. An alternative version of the template was designed for a target distributed system, namely a set of processorsrunning VxWorks[387] connected by a network. VxWorks is a Unix-like single-user O.S.for real-time development work, which comes into the class of priority-driven O.S. with enhanced time services [216]. VxWorks is the market leader in real-time operating systems. VxWorks includes a performance simulator, and Java modules (with Jini sup-
2’Lightweight process’ was Sun Microsystem’s name for a thread. IEEE POSIX standard (P1003.1~) threads (pthreads) [171] are implemented on the later Solaris 2 O.S. [218] also from Sun. but are not The signal handling and scheduling schemes vary in pthreads fundamentally different from the viewpoint of an implementation of a data farm. Note that POSIX threads are implemented in Solaris 2 [189] as user-level threads that act through an intermediary thread (also called a light-weight process) which multiplexes a number of threads on to a limited number of kernel threads.
102
TEMPLATE-BASED
IMPLEMENTATlON
port). However, inhouse kernels as opposed to commercial operating systems predominant in this market. 3 In VxWorks, there are no heavyweight processes,only threads with optimized context-switching and responseto events. The data-farm template module is written in ‘C’, cross-compiled on a PC running the Windows 95/NT O.S. and loaded and linked on attached 6803OK boards. The 68030 microprocessor [345], has an instruction set with testand-set and compare-and-swap, suitable for implementing semaphores which indeed are a built-in feature of VxWorks. The 6803OK boards are linked by an Ethernet LAN, with VxWorks providing a source-compatible BSD 4.3 socket API for using the network. There are versions of VxWorks for a variety of embedded microprocessors4, such as (in 1993) the MC68040, the SPARC and SPARClite, the Intel i960, MIPS R3000, by 1997, the Pentium Pro, and more recently for smart devices. A current large embedded system would consist of a rack of PowerPCs connected by Myrinet (already mentioned in Chapter 2). The relationship between such a system and a cluster of PCs (with FPGA accelerators) linked by Myrinet (the Tower of Power from Virginia Polytechnic Institute) is discussedin [181]. 7.4.1
Common
implementation
issues
Figure 7.1 is an exemplar multi-threaded structure which implements the design principles. All of the features were explicitly put in place on the Unix version of the data-farm template. Urgent messageswere implemented solely on the Unix system as they are not an essential feature. As I/O is efficiently buffered on Unix systems [189], the provision of a separate I/O thread may be nugatory. On the Paramid system, thread scheduling is implicit. Further, there was no need for messagerecovery for multicast messages.The VxWorks system version of sockets does not implement network broadcasts, but communication is asynchronous and thread-specific. Thread scheduling is user selectable, either priority-based with preemptive options or round-robin. In designing the worker module an initial consideration was the nature of messagetraffic. Messages occur in two parts: a tag and the body of the message. The tag must include: the size of the messageto follow; a type indicating whether a messageis a broadcast or a request for processing; and a messagenumber. The messagenumber is intended to signal to the receiver which data structure to position for the accommodation of the second part of the message. The messagenumber might also be used for other purposes. The body of the messageshould include a function number as the first field of the message,but otherwise the messagerecord structure was undetermined. Compared to a sequential version of a program, excessive data movement may
3For a review of other real-time operating systems refer to [313]. 4A characteristic embedded microprocessor such as the i960 requires a minimum of auxiliary chips.
TARGET
Farmer
MACHINE
process
Worker
/
\ threads:
103
MPLEMENTATION
Process
/ threads:
/
data-distribution control
loop -<[
output
buffering
]
( urgent
recepuon
)
recovery
thread
thread
scheduler
Fig. 7.1
Simplified
request
scheduler
layout of a single farm.
be involved in the formation of messagesfor a parallel implementation. The application programmer will need to balance utility with complexity. The potential for a large number of different messageswasthe reason for the restriction to a rigid messageformat. Each work request messageis serviced by one application thread function (Fig. 7.2). In ‘C’ it is possible to use an array of function pointers to which the function number forms an index. Though not entirely satisfactory, data and parameters are passedto the function as globals. The result is that each function can be referenced simply by a number. From the figure it will be seen that the application thread was divided between a public interface and a private part into which different functions can be slotted. This makes it possible to extract the functions from sequential code constructed with structured programming and place them into the slots. Circular incoming and outgoing buffers service each application process (Fig. 7.3). Access-contention control was set up through semaphores. Separate buffer slots are kept for tags, otherwise there is a danger of the small slots needed for tags being expanded to handle larger messages.Buffers are automatically enlarged by dynamic memory allocation.5 To avoid the possibility of deadlock if a series of broadcast messagewere to arrive at asynchronous 5Systems with strict deadlines might wish to allocate all memory before the main processing cycle as memory allocation can be a costly operation in terms of time, is not a fixed cost, and may occur at unforeseen times.
104
TEMPLATE-BASED
MPLEMENTATION
I
Global data structures
.: Message4 :. 4 i . * ~------------L-- 1
. Public
Request type 1 Request type 2 Request type n
1 memory area only,1
c----------\ I
i
Private
: Terminate II fI Function 1 I [ Function 2 I II I I I I I I I I
I I I I I I I I I
i II i II : I I I I I I I I I I I
i Fun&ion n II --,,,,,,,-,-, . .-...__._.._..........-...................-...................-..-..-.-...........-..Generic worker Fig. 7.2
Generic application
thread.
intervals, at least one extra buffer slot is needed over and above the number of messagessent out at loading time. This method is a variant of an algorithm which is proven in [311].
7.5
‘NOW’ IMPLEMENTATION
FOR LOGIC DEBUGGING
A thread system was first established on the worker and farmer modules using the LWP library. Context switching is within a Unix heavyweight process. A process’s stack is multiplexed by the LWP library between the various LWPs. The LWP library maintains minimal state for each LWP, for instance a program counter and the LWP’s priority, so that if a LWP’s time-slice is interrupted it does not complete the remainder of the time slice when it is rescheduled. This seemed appropriate for the data farm, but other thread systems (e.g. VxWorks) maintain more state. To allow for the rudimentary
‘NOW’
multicast channel
IMP1 EMENTATION
FOR LOGIC
i data ; channel
DEBUGGING
105
Buffer-in and buffer-out are threads.
1 I I
I1 i
I I I I I I I 1
another worker E
I I I I I I I
/f
I
least one buffer slot is kept empty of work requests so as to avoid the possibility of deadlock if a broadcast should arrive.
At
Fig. 7.3
buffer slots is experimentally determined from the work-flow for an application.
Generic buffer.
nature of the thread system, the Unix version of the template caught any stack overflows between LWPs.’ The data-farm design calls for pre-emptive communication threads and background round-robin thread scheduling. However, the SunOS LWP library is non-preemptive and priority-driven. A compromise was to set-up all normal threads to be switched by a round-robin scheduler, but after polling for a communication event a communication thread immediately deschedulesif no response occurs. Round-robin context switching was provided in the farm template by a software scheduler LWP:
while
(TRUE) sleep (TIME-QUANTUM) reschedule active process queue
%tack partitions can be red-zone protected by the LWP library. A red area of memory Therefore, any attempts to read, write, is defined as being unallocated and uninitialized. or free a red restrictions.
zone will
throw
up an error.
Other
colors
of memory
have
a subset
of these
106
TEMPLATE-BASED
1MPLEMENTATlON
A time quantum of 100~s was satisfactorily used in tests. External communication was implemented by means of the BSD socket API. An effort was made to tune communication within the data farm by utilizing some of the specialist features of the API in coordination with the LWP library. The f cntl system call enables socket communication to be made non-blocking, as was required in the design model. Reliable stream communication occurs via the underlying TCP/IP transport-level protocol. However, care was still needed in coding the template channel primitives as messagecontents could be lost if either the messagesystem call unblocked or if the data stream delivered an incomplete section of the intended message. Standard Unix has a global error number, errno, which in this instance was important as it indicates messagestatus. Therefore, the global errno was mapped to a local LWP copy. Conveniently, the LWP context in the relevant template threads was augmented to include errno by means of a LWP library facility. The template sockets were set so that Nagle’s algorithm [254] was not applied (whereby small messagesare delayed in order to avoid congestion on long-haul networks). The f cntl call also can set a socket to give an asynchronous responseand this facility was employed for broadcast and urgent sockets. The socket was awakened by a BSD Unix I/O signal. Where more than one reception socket is needed then it is necessary to inspect each socket in turn as an I/O signal occurs on a per-process basis. In order to map signals to threads an agent was needed. An LWP agent sleepsat the highest priority until a signal arrives. The agent then makes a rendezvous with its associated LWP. The template broadcast thread or urgent thread services all pending communication before descheduling. Internal communication between the template threads, principally between the buffer threads and an application thread, was implemented by wrapping the LWP rendezvous to resemble a CSP channel. Unlike CSP’s channel, the LWP rendezvous is asymmetric. The designated sender passesthe addresses of an input buffer and an output buffer. The receiver LWP is rescheduled when the sender and the receiver reach the rendezvous point. The sender is rescheduled by the receiver once it has processed the buffers in any way. In the template implementation, the rendezvous was used simply for synchronization, so as to avoid an extra memory-to-memory copy. Data were transferred not by the rendezvous buffer mechanism but by fast memory transfer through ANSI ‘C’ memcpyinto global buffers. The template design specifies semaphore regulation of global buffers. However, Sun’s LWP library supports a monitor data structure with associated condition variables, which can be signaled. The action of the monitor is hidden through mutex variables. Counting semaphore wait (p) and signal (v) were fashioned from this primitive, illustrated in pseudo-code: wait: lock mutex
‘NOW’
/MPlEMElVTATION
FOR LOGIC
DEBUGGlNG
107
while (semaphore count is zero) (wait on semaphore condition variable) decrement semaphore count unlock mutex
signal:
lock mutex if
(semaphore count is zero) (set contention) else (unset contention} increment if
signal
count
(contention is set) (signal on semaphore condition
variable)
unlock mutex
No LWP is scheduled while another LWP is within either critical region, marked by the mutex, unless that LWP has been descheduled by wait. The queue to the semaphore is assumedto be FIFO. The nondeterministic operator was simulated in the template by the socket API select system call. The system call is unblocked by only using select in its polling form. As more than one socket may become ready for communication a routine was added to shuffle the order of selection according to a suitable and ideally random re-ordering. The intention was to ensure fairness to the selection of inputs. An alternative which was easy to implement was to move the current socket tag to the end of a list and move all the other tags forward one step. Message records were implemented by means of socket API vectored messages. Again, care was needed in writing routines for vectored messagesas it is possible for one or more of the parts of the vectored messageto arrive incomplete or not at all. The template code identifies which part of the vectored messagehas been dropped and picks up the rest of the messagestream. Broadcasts under BSD Unix are restricted to datagrams, for which delivery is not guaranteed. In tests, it was found that if successive broadcasts were sent there was a distinct possibility that broadcast frames would be
108
TEMPLATE-BASED
MPLEMENTATION
dropped.7 Therefore, the template incorporates robust checking. A recovery mechanism was necessary whereby after a timed interval a repeat request is sent. The timer was implemented by an alarm-clock interrupt. Each work message is stamped with the sequence number of the last broadcast to be sent. The broadcast thread maintains the sequence number of the last consecutive broadcast. It will then be evident if either a broadcast has been dropped or if a work message has overtaken a broadcast.8 The application programmer can prepare application code for incorporation into the template largely as if a worker process and the farmer process are single-threaded. The main exception is non-reentrant system calls [189] which should be avoided. The programmer can check the working of the application by reference to an event-trace which is time-stamped (or event-stamped) by a global clock. [112] gives a simple example of this approach whereby the code for a one-dimensional FFT was inserted in a worker template. Two farms were formed for the row/column processing stages of a two-dimensional transform. The code for the intervening matrix transpose formed a centralized stage catered for in a single farmer. The whole formed a three-stage 2-D FFT parallel pipeline. A scalar logical clock was not difficult to implement as it requires no extra message passing. The clock update algorithm required a minimum of calculation: Initialize: Set logical-clock to zero. Set clock increment (usually
to one).
Logical-clock procedure: If (message is a receive) (let logical-clock = maximum(logical-clock, Increment If
received-time-stamp))
logical-clock
(message is a send) (time-stamp message}
The farm system does not have simultaneous messages arriving, because otherwise the tie would be broken by the process identities. The scalar clock may be extended to a vector clock, which allows ordering of internal events as long as the processes concerned are causally related (by a message). The components of the vector are the sending process’s most recent scalar clock for all processes. The overhead from passing a vector of clocks with the most recent timings at any one process for all other processes grows with the num7The reception socket was again in unblocking and asynchronous mode. 8Duplicate broadcasts pose no extra difficulty.
TARGET
MACHINE
1MPLEMENTATlONS
FORPERFORMANCE
TUNlNG
109
ber of processes, while the scalar logical clock keeps a record with minimal perturbation. Generally, one should bear in mind that the pattern of message passing on a distributed system might be different to that of the target machine. The intention is to catch unexpected orderings. A scalar logical clock is also employed in the ATEMPT trace system [135]. At this stage in development, the trace display was via the post-mortem visualizer, ParaGraph [153]. A standard trace file [392] format was used, compatible with ParaGraph. The format includes a broadcast field but does not include multicast, which is understandable as the destinations are difficult to specify if the record size is restricted. However, if several farms are employed within the PPF pattern, multiple per-farm multicasts can take place. These were emulated by creating multiple messagerecords in the trace file. Multicasts were stamped with the source and a message-type code not used elsewhere. Post-processing changed the multicast messageto a set of messageswith the same timestamps but different destinations (ParaGraph does not assumea monotonic clock). Initialization and termination messagescould also be removed at trace-file post-processing time. Figure 7.4 is a screen-shot showing a trace taken from a single-farm test run. The plotted lines represent messagesfrom one process to another. The sign of the gradient (the slope direction) of the line indicates the direction of communication. Processor 0 hosts the farmer process, which initially loads three buffer slots with work on each of four worker processes. At each cycle of subsequent processing: a broadcast is sent; a request for work in the form of processed work is serviced; and an urgent signal is sent to one of the processes (on processor two). g Because broadcast messages,urgent messagesand normal work messagesare handled by separate threads within the worker process it is necessary to maintain distinct logical clocks for each of these threads.lO At the end of processing, the trace files for each thread and each process are merged and subsequently sorted into order.
7.6
TARGET MACHINE IMPLEMENTATIONS PERFORMANCE TUNING
FOR
Apart from multicast, most of the template communication primitives were already present in Inmos parallel ‘C’. The existing system software (Fig. 7.5) includes servicing of run-time I/O requests on all modules by means of a run-time executive (RTE). I/O is multiplexed onto the SCSI link to the host. The multiplexer channels are set up conveniently by VCS software. Only one process running on the 860 can communicate with the system interface
gThe urgent signal is an optional facility provided to enable a response to interrupts. l*The size of each trace-record file data structure should be regulated in order not to perturb the application which for example could occur through excessive paging.
110
TEMPLATE-BASED
MPL EMENTATION SPACETIME
DItGRAtl
P R 0 C E S S 0 R N U M e E R
TIME
51
Fig. 7.4 Logical clock trace of a farm test run. program running on the transputer. Naturally, this process was the worker application thread which was supplied with a public interface and a set of protected services, exactly as in the Unix version. Instrumentation was the main sub-system missing from the Paramid system software (though console monitoring of link activity is available and useful). The existing interface program was enhanced with a trace recorder and synchronized clock process (Fig. 7.6). To substitute the new interface program, the application object code is booted onto the i860 network and in a second loading phase the transputers are booted up. The interface program then restarts the i860. The local clocks are updated by periodic pulses from a monitor process. On receipt of a messagefrom the i860 application program, a trace record is generated, time-stamped by a call to the local clock. All the processesmentioned run at high-priority as it is important to service the i860. Where a trace is made on a transputer-based process, the clock should also run at high priority so as to reduce the interrupt latency, which for a single high-priority process is 58 processor cycles (2 ps). If need be, an additional process is run at low priority [32] with the purpose of monitoring processor activity. The process simply counts each time it is activated before descheduling itself. If the processor monitor is called relatively frequently the processor can be assumed to be relatively idle. Internal monitoring of processesis not necessary if there is limited competition for the transputer’s time. If the interface program could determine the destination or source of a messageby its contents these arrangements would be enough. At present, the communication primitive on the i860 is augmented to include these details? Many of the external communication features of the data-farm template were implemented in VxWorks exactly as in the Unix-based system. A data1
llThe Paramid shared-memory data structure can be changed usually without the pre-compiled kernel routines.
disturbing
TARGET
MACHINE
IMPLEMElVTATIONS
FORPERFORMANCE
To the host
-
II
Worker
1
111
,,
Ivcs
h
TUNING
unspun / I \ I II I \\\\\ / \\\ I,II
\
/--Y2&.ppeci
memory
VCS = Virtual Channel System RTE = Run-Time Executive
I I I I I
Fig. 7.5
Paramid
\ \ \ \ \
system software.
farm worker module, consisting of application and buffering threads is spawned from an initializing thread. Remote spawning was accomplished by writing an iterative server as RPC daemons are unavailable in VxWorks. The internal state of the VxWorks system is almost completely user-accessibleand in many cases user modifiable. For example, the O.S. clock is programmable and cache flushing is specifiable. In fact, the data-farm template structure is needed to avoid anarchic use of the facilities. Internal channels were emulated in VxWorks, by a message queue primitive which when single-spaced fulfills the same purpose. A wrapper was provided to make it appear that the channel is used for intra- and inter-processor communication. The queueing discipline on semaphoresis selectable, though for compatibility with the data-farm template in the other environments a FIFO discipline was chosen.
123
TEMPLATE-BASED
1MPL EMEAiTATlON
Time reply Time “d request , ,+ t ’ / Transputer , / / I ,’
i860
Trace-file (Weaklyshared data) Q.. ..
-.*. *.*.
/
*.-. *.
*.*. *.*. -. ‘+
<---------...--Return trace file, which is then merged into global file.
Command
I/O reauest
Message destinatio
Data sup&y w Channel request 4 Terminate
/1 Reply
processing
(trace is returned
on
\
I Application Library
4
process calls
------: ---- +-----t
Request f * Command-processing, trace-recorder and synchronized clock and process monitor are threads
\
Over-lappbd
memory
i
* Communication within the transputer is by means of internal channels
Fig. 7.6
7.7
PATTERNS
The Paramid
monitoring
layout.
AND TEMPLATES
It is possible to construct larger software objects, frameworks, by grouping software components, just as a pipeline of data-farm templates forms a PPF. High-level architectural patterns with design reuse in mind [122] are a recent informal feature of the object-oriented approach to software development. A pattern is an abstract design which can be reapplied in a variety of situations. For example the model-view-controller and presentationabstraction-controller [46] are two abstract patterns for organizing graphical user interfaces. However, adoption of pattern-oriented software has not been widespread in parallel computing because of an emphasis on performance and hence on customized solutions. On the contrary, a PPF can be seen as a pattern; see Fig. 7.7. Certainly, viewing software in architectural terms has been widely perceived as beneficial.
1
;111 worker
data-farm
Fig. 7.7
7.8
data-farm
PPF as a pattern.
CONCLUSION
The benefit of a clearly defined design process is increased software productivity, and there is no reason why parallel computing should not share in this gain. Embedded software for parallel systems can particularly benefit from this endeavor as embedded software is expensive to produce and in some cases,for example in avionics, is continually reused over very long periods of time. A way of capturing the features of the design that can be reproduced on distributed and parallel systems alike is required. Presently, the cluster or NOW running as a distributed system is a low-cost way of testing the parallel logic of an application, once it has been partitioned. A workstation holds the core sequential application algorithm, while the cluster implementation [194] holds the core parallel version of the application. Target versions running on performance-oriented hardware are spawned as and when they are needed. Again the template captures the same functionality as was present in the parallel logic version. This chapter has detailed how the farm design, which is a relaxed version of CSP, can be mapped onto two typical distributed development environments and also more generally onto a range of target embedded parallel systems.
Part III
Case Studies
8 Application
Examples
The essence of PPF is practicality. In this chapter, four case studies are presented in which PPFs have been used to parallelize substantial applications. Here substantial means that the code lengths are significant and, moreover, there are a number of algorithmic components. To reiterate, while single algorithm implementations make convenient exemplars, in many ‘real-world’ applications the interaction of multiple algorithms is more significant in performance terms than any one algorithm. Nevertheless, in Chapter 9 a few small embedded PPF applications based on a single algorithm are presented. The case studies are related to image communication and vision. Two of the case studies are concerned with coders/decoders (codecs) for video sequences [347]. With the advent of Digital Versatile Disc (DVD) drives, video decoders are becoming widespread in consumer electronics. For example, the Advanced Graphics Protocol (AGP) Bus [96] on PCs has provision for a decoder in order to reduce bus bandwidth or to read from a DVD. Similarly, Sony intends to provide an embedded decoder in the Emotion Machine IC for the Playstation [82]. Both decoders follow the MPEG-2 standard which in its general structure is closely related to H.261, discussed in the first case study. Hybrid video codecs, that is those codecs which make use of both transform and stochastic algorithms, are computationally asymmetrical. The decoder is simpler than the encoder (indeed is embedded within the encoder) and, therefore, as it has a regular structure, has been implemented in hardware at the VLSI level. Before the transfer to VLSI takes place, algorithms have to be tested against a range of sample video streams, necessitating the type of accelerated coding performance evaluation outlined in Chapter 1, Section A.l. 117
128
APPLlCATlON
EXAMPLES
Fully featured encoders are more difficult to transfer to hardware. The H.261 encoder is also difficult to parallelize as a PPF because of the synchronous constraint imposed by previous picture feedback and quantization level feedback. Nevertheless it was possible to overcome this problem, in the case study, by employing a folded-back pipeline. Section 8.1 is a comprehensive study of an H.261 PPF. The H.263 encoder, considered in Section 8.2, is capable of a 6dB peak signal-to-noise ratio (PSNR) improvement in performance over H.261 [130] when used in advanced mode. However, the improvement is at a cost in software complexity. The next case study, Section 8.3, is connected to the work on codecs in the sense that facial recognition could be applied to a stream of video surveillance images. In fact, for recognition purposes a single frame is searched for a head image. Subsequently, the face and face features are transformed to a feature space where identification is easier. Depending on the application, various real-time processing deadlines may exist. Finally, Section 8.4 contains three case studies on optical flow, again using a stream of video frames to overcome reliance on any particular two frame sequence. Because of the volume of data, and the computational intensity, real-time operation of optical flow is still far away for some of the proposed detection systems. Buffering of up to nineteen frames is required, whereas the preceding frame only is buffered for motion estimation in video codecs (with about eight frames in MPEG-like group-of-picture buffers). Whereas motion estimation in standard codecs is usually based on a 16 x 16 pixel macroblock, in optical-flow algorithms a motion vector for every pixel is sought. Therefore, parallelization aims to reduce the runtime both to facilitate further research, and to provide tolerable throughput in live applications of optical flow.
8.1 CASE STUDY
1: H.261 ENCODER
Figure A.6 shows a block diagram of the structure of an H.261 encoder. The H.261 coding algorithm [37, 1301 is a hybrid algorithm which utilizes motioncompensated differential p