A Class of Optimal Structures for Node Computations in Message Passing Algorithms
share
Consider the computations at a node in the message passing algorithms. Assume that the node has incoming and outgoing messages 𝐱 = (x_1, x_2, …, x_n) and 𝐲 = (y_1, y_2, …, y_n), respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing 𝐲 from 𝐱, where each y_j, j = 1, 2, …, n is computed via a binary tree with leaves 𝐱 excluding x_j. We have three main contributions regarding this class of structures. First, we prove that the minimum complexity of such a structure is 3n - 6, and if a structure has such complexity, its minimum latency is δ + ⌈log(n-2^δ) ⌉ with δ = ⌊log(n/2) ⌋. Second, we prove that the minimum latency of such a structure is ⌈log(n-1) ⌉, and if a structure has such latency, its minimum complexity is n log(n-1) when n-1 is a power of two. Third, given (n, τ) with τ≥⌈log(n-1) ⌉, we propose a construction for a structure which likely has the minimum complexity among structures with latencies at most τ. Our construction method runs in O(n^3 log^2(n)) time, and the obtained structure has complexity at most (generally much smaller than) n ⌈log(n) ⌉ - 2.
READ FULL TEXT