This paper presents an algorithm for implementing optimal
hardware-based multicast trees, on networks that provide hardware
support for collective communication. Although the underlying
methodology is general enough to be applied in other, present and
future, technologies, the Quadrics network has been chosen as a
state-of-the-art interconnect where applying hardware-based multicast
trees. The proposed mechanism is intended to improve the performance
of the collective communication patterns on the network, in those
cases where the hardware support can not be directly used, for
instance, due to some faulty nodes. This scheme provides significant
reduction on multicast latencies compared to the original system
primitives, which use multicast trees based on unicast
communication. A backtracking algorithm to find the optimal solution
to the problem is presented. In addition, a greedy algorithm is
presented and shown to provide near optimal solutions. Finally, our
experimental results show the good performance and scalability of the
proposed multicast tree in comparison to the traditional unicast-based
multicast trees.