Irregular Wavefronts in Data-Driven Data-Dependent Computations.
Abstract
This paper considers networks in which the execution time of local cycles depends on the input data. Typically, this may occur if the local cycles contain branching statements. Although data driven networks are self-synchronized, and hence, local cycles are allowed to have different execution times, it is not obvious that the execution of the entire network may benefit from the fast execution of some local cycles. More specifically, internal data conflict may force a potentially short local cycle to wait extensively for its input. The study of speed and efficiency of data driven networks with data dependent operations is extremely hard due to the asynchronous nature of the networks. Hence, we suggest a technique for the estimation of a lower bound on the performance of such networks. Namely, we introduce a simpler, hypothetical, type of computations, which we call pseudo-systolic. It alternates between communication and processing phases. Clearly, the additional synchronization may only slow down execution, and hence, the analysis of pseudo-systolic computations provide upper bounds on the execution time of the corresponding data driven computations.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1986
- Accession Number
- ADA171151
Entities
People
- Rami G. Melhem
Organizations
- University of Pittsburgh