Irregular Wavefronts in Data-Driven Data-Dependent Computations

摘要

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.