Low-dimensional meshes:
Embeddings and communication algorithms

ABSTRACT

In this talk I will present an overview of our latest research results in the area of structural and communication properties of 2-D and 3-D meshes and tori. These orthogonal topologies have been widely studied for many years and there is an abundance of various results. I will focus on two specific problems, so that my talk will consist of two parts.

• I will review some recent advances in the area of tree embeddings and simulations of tree-based parallel algorithms on meshes. Then I will present several new results on embeddings and simulations of complete k-ary trees in 2-D and 3-D meshes.
• I will shortly summarize research results in the area of optimal gossip (all-to-all broadcast) algorithms for 2-D and 3-D meshes and tori. Then I will discuss some new results on time- and memory-optimal gossip algorithms in these networks, based on time-arc-disjoint spanning trees.

Bio

Pavel Tvrdik is an associate professor at the Czech Technical University (CTU) Prague, Department of Computer Science and Engineering (DCSE). He received CSc. (equiv. of PhD) from CTU in 1991. His research interests are in the area of parallel computing, architectures of parallel systems, communication algorithms, and interconnection networks. He is the head of Parallel Computing Group of DCSE CTU. He was awarded Fulbright Grant for Visiting Scholars in 1999 and he is currently visiting professor at University of Wisconsin-Madison, Computer Sciences Department. He is a member of IEEE and ACM.

Colloquia Series page.