An improved embedding of binary trees in a square reconfigurable array with spanning optical buses

This paper improves on the embedding of binary trees in a non-square Reconfigurable Array with Spanning Optical Buses (or RASOB), which was presented in [1]. Specifically, a binary tree of N² - 1 nodes is embedded in a square N × N RASOB to achieve an optimal expansion cost, while maintaining an optimal dilation cost of 1. Such an embedding also leads to the embedding of a larger binary tree having 2^k · N² - 1 nodes, which achieves optimal load-balance and an optimal dilation cost of 1.