Extended Abstracts of the 18th Symposium on Operation Research, Cologne, Germany, September 1-3, 1993.

Many computationally demanding problems do not exhibit high regularity. For this sake, a data-driven processor array, capable of executing any given algorithm, was recently suggested. An arbitrary parallel algorithm is written in a high-level language and directly mapped onto the array using a well- known mapping scheme. In the paper we analyze the mapping scheme and show that, in general, it results in a low area utilization. In particular, we show that algorithm mappings are horizontally overstretched across the array. Ideally, two directly data-dependent operations u and v would be mapped onto two neighbouring processors P(u) and P(v), respectively. However, in practice this is rarely the case. In fact, we show that the distance between P(u) and P(v) has an upper bound (m-1)(n-1)(m+n-2)/2(mn-1) = O(m+n), where m and n are the numbers of all data-dependent operations of u and v, respectively. Moreover, we show that this bound is a tight one. As a consequence, such algorithm mappings exhibit two disadvantages. First of all, since time complexity of routing is not negligible, execution slow down occurs due to remote communication between processors. Secondly, algorithm mappings may require a too large area. Based on the above analysis we designed several optimization methods and improved the algorthm mappings.