On the Flattest Common Supersequence Method for De

Authors: A K Laing R Cypher C A Duncan

Publish Date: 2013/06/18

Volume: 33, Issue: 5-6, Pages: 393-426

PDF Link

Abstract

In this paper we consider the problem of deadlockfree routing in arbitrary parallel and distributed computers We focus on asynchronous routing algorithms which continuously receive new packets to route and which do not discard packets that encounter congestion Specifically we examine what we call the deadlockfree routing DFR problem The input to the DFR problem consists of an arbitrary network and an arbitrary set of paths in the network The output consists of a routing algorithm which is a list of the buffers used along each of the paths The routing algorithm is required to be free from deadlock and the goal is to minimize the number of buffers required in any one nodeWe study the DFR problem by converting it into an equivalent problem which we call the flattest common supersequence FCS problem The input to the FCS problem consists of a set of sequences and the output consists of a single sequence that contains all of the input sequences as possibly noncontiguous subsequences The goal of the FCS problem is to minimize the maximum frequency of any symbol in the output sequenceWe present three main results First we prove that the decision version of the FCS problem is NPcomplete and has no polynomialtime approximation scheme unless P= NP An alternative proof is presented which shows that unlike the shortest common supersequence SCS problem the FCS problem is still NPcomplete for two input sequences This implies that approximation algorithms for FCS based on an exact pairwise merge are not possible Next we propose and experimentally evaluate a range of heuristics for FCS Our experimental results show that one of these heuristics performs very well over a wide range of inputs Lastly we prove that this heuristic is in fact optimal for certain restricted classes of inputs

Keywords: