Abstract In this paper, we propose a new erasure decoding algorithm for convolutional codes using the generator matrix. This implies that our decoding method also applies to catastrophic convolutional codes in opposite to the classic approach using the parity-check matrix. We compare the performance of both decoding algorithms. Moreover, we enlarge the family of optimal convolutional codes (complete-MDP) based on the generator matrix.

Maximum distance profile codes over finite nonbinary fields have been introduced and thoroughly studied in the last decade. These codes have the property that their column distances are maximal among all codes of the same rate and degree. In this paper, we aim at studying this fundamental concept in the context of convolutional codes over a finite ring. We extensively use the concept of p-encoder to establish the theoretical framework and derive several bounds on the column distances. In particular, a method for constructing (not necessarily free) maximum distance profile convolutional codes over Zpr is presented.

So far, in the area of Random Linear Network Coding, attention has been given to the so-called one-shot network coding, meaning that the network is used just once to propagate the information. In contrast, one can use the network more than once to spread redundancy over different shots. In this paper, we propose rank metric convolutional codes for this purpose. The framework we present is slightly more general than the one which can be found in the literature. We introduce a rank distance, which is suitable for convolutional codes, and derive a new Singleton-like upper bound. Codes achieving this bound are called Maximum Rank Distance (MRD) convolutional codes. Finally, we prove that this bound is optimal by showing a concrete construction of a family of MRD convolutional codes.

Maximum distance separable (MDS) block codes and MDS 1D convolutional codes are the most robust codes for error correction within the class of block codes of a fixed rate and 1D convolutional codes of a certain rate and degree, respectively. In this paper, we generalize this concept to the class of 2D convolutional codes. For that, we introduce a natural bound on the distance of a 2D convolutional code of rate k/n and degree δ, which generalizes the Singleton bound for block codes and the generalized Singleton bound for 1D convolutional codes. Then, we prove the existence of 2D convolutional codes of rate k/n and degree δ that reach such bound when n k(((I(δ/k)J + 2)(I(δ/k)J + 3))/2) if k f δ, or n k((((δ/k) + 1)((δ/k) + 2))/2) if k | δ, by presenting a concrete constructive procedure.

Convolutional codes are considered with code sequences modeled as semi-infinite Laurent series. It is well known that a convolutional codeCover a finite groupGhas a minimal trellis representation that can be derived from code sequences. It is also well known that, for the case thatGis a finite field, any polynomial encoder ofCcan be algebraically manipulated to yield a minimal polynomial encoder whose controller canonical realization is a minimal trellis. In this paper we seek to extend this result to the finite ring caseG= \BBZprby introducing a so-called ldquop-encoderrdquo. We show how to manipulate a polynomial encoding scheme of a noncatastrophic convolutional code over\BBZprto produce a particular type ofp-encoder (ldquominimalp-encoderrdquo) whose controller canonical realization is a minimal trellis with nonlinear features. The minimum number of trellis states is then expressed aspgamma, wheregammais the sum of the row degrees of the minimalp-encoder. In particular, we show that any convolutional code over\BBZpradmits a delay-freep-encoder which implies the novel result that delay-freeness is not a property of the code but of the encoder, just as in the field case. We conjecture that a similar result holds with respect to catastrophicity, i.e., any catastrophic convolutional code over\BBZpradmits a noncatastrophicp-encoder.

We study the isolated and combined effects of several latency-tolerance techniques for software-based distributed shared-memory systems (software DSMs). More specifically, we focus on data prefetching, update-based coherence, and single-writer optimizations for page-based software DSMs. Our experimental results with six parallel applications show that, when these techniques are carefully combined, they can provide running time and speedup improvements of up to 54 percent and 110 percent, respectively, on a cluster of eight PCs.

In this paper we propose and evaluate the Adaptive++ technique, a novel runtime-only data prefetching strategy for software-based distributed shared-memory systems (software DSMs).Adaptive++ improves the performance of regular parallel applications running on software DSMs by using the past history of memory access faults to adapt between repeated-phase and repeated-stride prefetching modes.Adaptive++ does not issue prefetches during periods when the application is not exhibiting one of these two types of behavior and is thus behaving irregularly.Through detailed execution-driven simulations of several applications, we show that our prefetching technique is very successful at reducing the data access overheads of regular applications running on the TreadMarks software DSM.Adaptive++ also reduces the overhead of applications that are not strictly regular but that exhibit periods of regularity.In terms of overall performance, our results show that Adaptive++ can provide speedup improvements as significant as 34% on 16 processors.A direct comparison against two runtime-only prefetching techniques proposed thus far shows that Adaptive++ is consistently competitive in terms of performance, while being able to optimize a larger set of applications.Our main conclusion is that Adaptive++ should definitely be considered by software DSM designers as an effective way of tolerating the overhead of remote data accesses.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commen: ial advantage and that copies bear this notice and the full citation on the fust page.To oopy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific pe-rmission and/or a fee.

In this paper we propose the use of a PCI-based programmable protocol controller for hiding communication and coherence overheads in software DSMs. Our protocol controller provides three different types of overhead tolerance: a) moving basic communication and coherence tasks away from computation processors; b) prefetching of diffs; and c) generating and applying diffs with hardware assistance. We evaluate the isolated and combined impact of these features on the performance of TreadMarks. We also compare performance against two versions of the Shrimp-based AURC protocol. Using detailed execution-driven simulations of a 16-node network of workstations, we show that the greatest performance benefits provided by our protocol controller come from our hardware-supported diffs. Reducing the burden of communication and coherence transactions on the computation processor is also beneficial but to a smaller extent. Prefetching is not always profitable. Our results show that our protocol controller can improve running time performance by up to 50% for TreadMarks, which means that it can double the TreadMarks speedups. The overlapping implementation of TreadMarks performs as well or better than AURC for 5 of our 6 applications. We conclude that the simple hardware support we propose allows for the implementation of high-performance software DSMs at low cost. Based on this conclusion, we are building the NCP2 parallel system at COPPE/UFRJ.