Off-the-shelf wireless sensing devices open up interesting perspectives for biomedical monitoring. Yet because of their limited processing and transmission capacities most applications considered to date imply either indoor real-time data streaming, or ambulatory data recording. In this paper we investigate the possibility of using disruption-tolerant wireless sensors to monitor the biomedical parameters of athletes during outdoor sports events. We focus on a scenario we believe to be a most challenging one: the ECG monitoring of runners during a marathon race, using off-the shelf sensing devices and a limited number of base stations deployed along the marathon route. Field experiments conducted during intra-campus sports events show that such a scenario is indeed viable, although special attention must be paid to supporting episodic, low-rate transmissions between sensors carried by runners and roadside base stations.

High-level synthesis (HLS) allows hardware to be directly produced from behavioral description in C/C++, thus accelerating the design process. Loop pipelining is a key transformation of HLS, as it improves the throughput of the design at the price of a small hardware overhead. However, for small loops, its use often results in a poor hardware utilization due to the pipeline latency overhead. Overlapping the iterations of the whole loop nest instead of only overlapping the innermost loop is a way to overcome this difficulty, but currently available techniques are restricted to perfectly nested loops with constant bounds, involving uniform dependences only. Using the polyhedral model, we extend the applicability of the nested loop pipelining transformation by proposing a new legality check and a new loop correction technique, called polyhedral bubble insertion. This method was implemented in a source-to-source compiler targeting HLS, and results on benchmark kernels show that polyhedral bubble insertion is effective in practice on a much larger class of loop nests.

Loop pipelining is a key transformation in high-level synthesis tools as it helps maximizing both computational throughput and hardware utilization. Nevertheless, it somewhat looses its efficiency when dealing with small trip-count inner loops, as the pipeline latency overhead quickly limits its efficiency. Even if it is possible to overcome this limitation by pipelining the execution of a whole loop nest, the applicability of nested loop pipelining has so far been limited to a very narrow subset of loops, namely perfectly nested loops with constant bounds. In this work we propose to extend the applicability of nested-loop pipelining to imperfectly nested loops with affine dependencies by leveraging on the so-called polyhedral model. We show how such loop nest can be analyzed, and under certain conditions, how one can modify the source code in order to allow nested loop pipeline to be applied using a method called polyhedral bubble insertion. We also discuss the implementation of our method in a source-to-source compiler specifically targeted at High-Level Synthesis tools.

HMMER is a widely used tool in bioinformatic, based on Profile Hidden Markov Models. The computation kernels of HMMER i.e. MSV and P7Viterbi are very compute intensive and data dependencies restrict to sequential execution. In this paper, we propose an original parallelization scheme for HMMER by rewriting their mathematical formulation, to expose the hidden potential parallelization opportunities. Our parallelization scheme targets FPGA technology, and our architecture can achieve 10 times speedup compared with that of latest HMMER3 SSE version, while not compromising on sensitivity of original algorithm.

Profile based Hidden Markov Model is a widely used tool in bioinformatics. While being very valuable to biologists, it is extremely compute intensive and suffers from prohibitive execution time. We propose an original parallelization scheme of the hmmsearch tool for FPGA technology. We show how to derive a flexible and generic hardware architecture which accelerates the hmmsearch main kernel by two orders of magnitude without modifying its original algorithm.

Because of the growing use of multimedia content over Internet, content-based image retrieval (CBIR) has recently received a lot of interest. While accurate search techniques based on local image descriptors exist, they suffer from very long execution time. We propose to accelerate CBIR on the RDISK machine, a cluster of FPGA-enhanced hard-drives, that follows the philosophy of smart-disks. Our platform combines coarse and fine grain parallelism thanks to the concurrent use of the cluster nodes and of a programmable logic device. The implementation of the CBIR application on this mixed hardware/software platform follows a strict methodology, that was validated on realistic data-set (image database of more than 30,000 images). This methodology allows us to adapt the original algorithm to suit a hardware implementation, and to select the values of some key design parameters to maximize global performance. Our preliminary results indicate that speed-ups between 120 and 200 could be obtained for a cluster of 32 nodes compared with a software implementation running on a standard desktop PC.

We introduce some basic principles for extending the classical systolic synthesis methodology to multidimensional time. Multidimensional scheduling enables complex algorithms that do not admit linear schedules to be parallelized, but it also requires the use of memories in the architecture. We explain how to obtain compatible allocation and memory functions for VLSI (or SIMD-like code) generation. We also present an original mechanism for controlling a VLSI architecture that has a multidimensional schedule. A structural VHDL code has been derived and synthesized (for implementation on FPGA platforms) using these systematic design principles. These results are preliminary steps to the hardware synthesis for multidimensional time.

Many computations can be modeled with systems of affine recurrence equations (SAREs) over polyhedral domains. We study the problem of scheduling individual computations of an SARE in the presence of reductions i.e., operations specifying the accumulation of a set of values to produce a single value. Reductions involve a commutative and associative operator and therefore, per se, do not impose any specific order. However, on realistic machines, operators have bounded fan-in and therefore an order of accumulation (serialization) is needed. Arbitrary serializations may adversely affect the running time of a program. We develop an algorithm to determine efficient serializations of all reductions. We illustrate our methods with two significant examples.

We present a set of verification methods to prove properties of parallel systems described by means of multidimensional affine recurrence equations. We use polyhedral analysis and transformation techniques together with theorem proving. Polyhedral techniques allow us to handle simple but otherwise costly proof steps, while theorem proving provides more expressivity and more complex proof techniques. This allows large, generic and structured systems to be verified. These methods are implemented in the M-MAlpha environment using the PVS theorem prover. 1

ALPHA is a functional language based on systems of affine recurrence equations over polyhedral domains. We present an extension of ALPHA to deal with sparse polyhedral domains. Such domains are modeled by Z-polyhedra, namely the intersection of lattices and polyhedra. We summarize the mathematical closure properties of Z-polyhedra, and we show how the important features of ALPHA, namely normalization, substitution, change of basis, are preserved in the extension.

We present a formal method for the verification of regular VLSI architectures. In our method, the behavioral specification of the chip and its implementation are first expressed in ALPHA, a language for the design of regular synchronous architectures. The behavioral specification as refined down to an abstract architecture description, while the implementation is simplified by induction techniques up to the same abstract architecture level. Verification is then done by matching both descriptions. This method has been successfully applied to check the correctness of a 300.000 transistor VLSI systolic chip named API69 for sequence comparison.>

Advances in VLSI technology make it possible to realize systems of very high complexity in a small volume of hardware using integration. In many application fields, it is necessary to implement certain algorithms, or even complete information processing systems, directly in silicon. Application domains which are likely to benefit are in the fields of signal processing and scientific computing. In this paper, we consider several steps which we believe to be essential in the design path of a special purpose architecture, and we present methodologies for achieving design requirements. These solutions are based on experience gathered in the Parallel VLSI Architecture group of IRISA.

Synthesis of systolic arrays, from formal specifications down to a chip, can be done using recurrence equations. The Alpha du Centaur environment that the authors present implements such a design trajectory. Programs, written in Alpha language, are rewritten Ising formal transformations (space-time reindexing, pipelining, control signal generation, etc.), and finally translated into a form suited to conventional VLSI design tools. The authors present the principle of systolic synthesis using Alpha du Centaur, and describe a systolic correlator that has been completely designed following this method.>

The authors present new scheduling techniques for systems of affine recurrence equations. They show that it is possible to extend earlier results on affine scheduling to the case when each variable of the system is scheduled independently of the others by an affine timing-function. This new technique makes it possible to analyze systems of recurrence equations with variables in different index spaces, and multi-step systolic algorithms. This theory applies directly to many problems, such as dynamic programming, LU decomposition, and 2-D convolution, and it avoids in particular preliminary heuristic rewriting of the equations.>

We describe Alpha du Centaur (ADC), a prototype environment for the design of parallel regular algorithms. In ADC, a program is specified using the Alpha language, using system of parameterized linear recurrence equations. The goal of ADC is to make it possible to transform the initial specifications into a parallel algorithm, that is to say, another system of recurrence equations, in which the time and the space index are separated.

A systolic architecture is proposed for the triangularization by means of the Gaussian elimination algorithm of large dense n*n matrices over GF(p), where p is a prime number. The solution of large dense linear systems over GF(p) is the major computational step in various algorithms issuing from arithmetic number theory and computer algebra. The proposed architecture implements the elimination with partial pivoting, although the operation of the array remains purely systolic. Extension of the array to the complete solution of a linear system Ax=b over GF(p) is also considered.>

We propose two systolic architectures for the Gaussian triangularization and the Gauss-Jordan diagonalization of large dense nxn matrices over GF(p), where p is a prime number. The solution of large dense linear systems over GF(p) is the major computational step in various algorithms issued from arithmetic number theory and computer algebra. The two proposed architectures implement the elimination with partial pivoting, although the operation of the array remains purely systolic. The last section is devoted to the design and layout of a CMOS 8 by 8 Gauss-Jordan diagonalization systolic chip over GF(2).

An integrated circuit used as a basic cell of a systolic array for speech recognition is described. An array of hundred such chips can support real-time recognition of utterances for a vocabulary containing up to 1800 words. The recognition algorithm is based on Bahl and Jelinek stochastic modeling of the errors made during the phonetic analysis of speech. The chip has been designed using 5 microns NMOS technology, and contains 12,000 transistors. We successively present the algorithm, the organization of the array, the internal architecture of the chip, and finally, the expected performances of the machine.

A systolic algorithm for connected word recognition (CWR) using dynamic time warping (DTW)Qtechnique is described. The algorithm relies upon an iterative method for finding the sequence of connected words that minimizes DTW distance to a given utterance. This method allows simultaneous computation of the best connected word sequence regardless of its number of words. A parallel implementation of the method is also proposed. Basically it uses a linear network of identical very simple processors. It is also explained how this network may be connected to a recently proposed DTW net-word implementing DTW algorithm. The machine resulting from this interconnection constitutes a highly parallel connected word recognition device. Such a device has a regular structure involving only local communication between very simple processors. This suggests a VLSI implementation of the device. This issue is also discussed.

We describe in this paper the comprehension part of a man-machine dialog system which performs automatic inquiry in a limited domain. The comprehension part involves a semantic interpreter and a dialog manager. The extraction of the semantic information conveyed by a sentence is based on an interpretation of the parse-tree; the semantic knowledge is represented by transformation rules associated with the production rules of a semantic context-free grammar. The pragmatic model, which has been designed with respect to its recognition environment, is able to take into account some particularities of the oral conversation (ellipsis, unexpected information), in order to make the dialog as natural as possible. It also makes predictions about possible user's replies to assist recognition and semantic interpretation.

This paper gives a description of a syntactic analyzer, which is used for continuous speech recognition. After the words have been located in a sentence by a lexical analyzer, the syntactic analyzer makes a bottom-up parsing, evaluating all the possible solutions, according to a context-free grammar. The analyzer has been designed to make up for some errors which had occured in the phonemic analysis, such as the omission or the insertion of phonemes, resulting in an inadequate segmentation of the words in a sentence. It also allows in some cases to complete sentences for which a word is missing. We have tested the program on a hundred sentences from simple languages (vocabularies of 50 to 100 words) : the present version of the analyzer allows the recognition of up to 50-60% of the sentences. It only takes a few seconds to analyze a sentence.