The DAP architecture is particularly well matched to calculations on 2-D arrays of data such as raster scanned images and digital terrain representations based on a regular grid. Although there are more compact chained-vector representations of terrain elevation and 'cultural' features such as rivers, roads, urban areas and forests etc., the decreasing cost of digital memory now makes it feasible to ally the more direct grid representation with the massive parallelism of a DAP to attack problems such as determining lines-of-sight (LOS) and route optimisations. Moreover the parallelism of the machine, using one or more thousands of processing elements (PEs) is far less than the typically millions of pixels of terrain data so that there is ample scope for targetting the PEs on useful sectors of data. The authors show how a DAP machine can readily be programmed to rapidly obtain optimum routes across a complex terrain and the authors indicate how the cost functions used could easily be generalised to include visibility of the route from remote points on the terrain as well as local functions related to gradient, negotiating obstacles using available roads etc. However higher order SIMD parallelism barely pays its way, achieving only a small speedup factor over a conventional sequential processor which can utilise more efficient algorithms in the sense of requiring many fewer operations. MIMD parallelism is likely to be more effective than SIMD in this case.
Route optimisation and computation for terrain models on distributed array processor (DAP)
Wegoptimierung und Berechnung für Geländemodelle mit verteilten Array-Prozessoren (DAP)
1989
6 Seiten, 13 Quellen
Aufsatz (Konferenz)
Englisch