Research Initiation Award: Graph Embeddings, Network Emulations, and Parallel Computer Architecture

This project studies graph embeddings and network emulations, two areas which have proven to be quite useful in the theoretical analysis of parallel architectures. The goals of the research include increasing understanding of the relative computational strengths of different interconnection network structures by proving new embedding and emulation results, and also studying more closely the relationship between graph embeddings and other more general notions of network emulation. In addition, problems in the related area of efficient mapping of parallel algorithms to parallel architectures, are studied.