Scheduling dynamic dataflow graphs with model checking

With the shift towards many-core computer architectures, dataflow programming has been proposed as one potential solution for producing software that scales to a varying number of processor cores. Programming for parallel architectures is considered difficult as the current popular programming languages are inherently sequential and introducing parallelism is typically up to the programmer. Dataflow, however, is inherently parallel, describing an application as a directed graph, where nodes represent calculations and edges represent a data dependency in form of a queue. These queues are the only allowed communication between the nodes, making the dependencies between the nodes explicit and thereby also the parallelism. Once a node have the su cient inputs available, the node can, independently of any other node, perform calculations, consume inputs, and produce outputs. Data ow models have existed for several decades and have become popular for describing signal processing applications as the graph representation is a very natural representation within this eld. Digital lters are typically described with boxes and arrows also in textbooks. Data ow is also becoming more interesting in other domains, and in principle, any application working on an information stream ts the dataflow paradigm. Such applications are, among others, network protocols, cryptography, and multimedia applications. As an example, the MPEG group standardized a dataflow language called RVC-CAL to be use within reconfigurable video coding. Describing a video coder as a data ow network instead of with conventional programming languages, makes the coder more readable as it describes how the video dataflows through the different coding tools. While dataflow provides an intuitive representation for many applications, it also introduces some new problems that need to be solved in order for data ow to be more widely used. The explicit parallelism of a dataflow program is descriptive and enables an improved utilization of available processing units, however, the independent nodes also implies that some kind of scheduling is required. The need for efficient scheduling becomes even more evident when the number of nodes is larger than the number of processing units and several nodes are running concurrently on one processor core. There exist several data ow models of computation, with different trade-offs between expressiveness and analyzability. These vary from rather restricted but statically schedulable, with minimal scheduling overhead, to dynamic where each ring requires a ring rule to evaluated. The model used in this work, namely RVC-CAL, is a very expressive language, and in the general case it requires dynamic scheduling, however, the strong encapsulation of dataflow nodes enables analysis and the scheduling overhead can be reduced by using quasi-static, or piecewise static, scheduling techniques. The scheduling problem is concerned with nding the few scheduling decisions that must be run-time, while most decisions are pre-calculated. The result is then an, as small as possible, set of static schedules that are dynamically scheduled. To identify these dynamic decisions and to find the concrete schedules, this thesis shows how quasi-static scheduling can be represented as a model checking problem. This involves identifying the relevant information to generate a minimal but complete model to be used for model checking. The model must describe everything that may affect scheduling of the application while omitting everything else in order to avoid state space explosion. This kind of simplification is necessary to make the state space analysis feasible. For the model checker to nd the actual schedules, a set of scheduling strategies are de ned which are able to produce quasi-static schedulers for a wide range of applications. The results of this work show that actor composition with quasi-static scheduling can be used to transform data ow programs to t many different computer architecture with different type and number of cores. This in turn, enables dataflow to provide a more platform independent representation as one application can be fitted to a specific processor architecture without changing the actual program representation. Instead, the program representation is in the context of design space exploration optimized by the development tools to fit the target platform. This work focuses on representing the dataflow scheduling problem as a model checking problem and is implemented as part of a compiler infrastructure. The thesis also presents experimental results as evidence of the usefulness of the approach.

Caractérisation électro-clinique des convulsions fébriles et risque d’épilepsie

Environ 2-3% d’enfants avec convulsions fébriles (CF) développent une épilepsie, mais les outils cliniques existants ne permettent pas d’identifier les enfants susceptibles de développer une épilepsie post-convulsion fébrile. Des études ont mis en évidence des anomalies d’EEG quantifiée, et plus particulièrement en réponse à la stimulation lumineuse intermittente (SLI), chez des patients épileptiques. Aucune étude n’a analysé ces paramètres chez l’enfant avec CF et il importe de déterminer s’ils sont utiles pour évaluer le pronostic des CF. Les objectifs de ce programme de recherche étaient d’identifier, d’une part, des facteurs de risque cliniques qui déterminent le développement de l’épilepsie après des CF et, d’autre part, des marqueurs électrophysiologiques quantitatifs qui différencieraient les enfants avec CF des témoins et pourraient aider à évaluer leur pronostic. Afin de répondre à notre premier objectif, nous avons analysé les dossiers de 482 enfants avec CF, âgés de 3 mois à 6 ans. En utilisant des statistiques de survie, nous avons décrit les facteurs de risque pour développer une épilepsie partielle (antécédents prénataux, retard de développement, CF prolongées et focales) et généralisée (antécédents familiaux d’épilepsie, CF récurrentes et après l’âge de 4 ans). De plus, nous avons identifié trois phénotypes cliniques distincts ayant un pronostic différent : (i) CF simples avec des antécédents familiaux de CF et sans risque d’épilepsie ultérieure; (ii) CF récurrentes avec des antécédents familiaux d’épilepsie et un risque d’épilepsie généralisée; (iii) CF focales avec des antécédents familiaux d’épilepsie et un risque d’épilepsie partielle. Afin de répondre à notre deuxième objectif, nous avons d’abord analysé les potentiels visuels steady-state (PEVSS) évoqués par la SLI (5, 7,5, 10 et 12,5 Hz) en fonction de l’âge. Le tracé EEG de haute densité (128 canaux) a été enregistré chez 61 enfants âgés entre 6 mois et 16 ans et 8 adultes normaux. Nous rapportons un développement topographique différent de l’alignement de phase des composantes des PEVSS de basses (5-15 Hz) et de hautes (30-50 Hz) fréquences. Ainsi, l’alignement de phase des composantes de basses fréquences augmente en fonction de l’âge seulement au niveau des régions occipitale et frontale. Par contre, les composantes de hautes fréquences augmentent au niveau de toutes les régions cérébrales. Puis, en utilisant cette même méthodologie, nous avons investigué si les enfants avec CF présentent des anomalies des composantes gamma (50-100 Hz) des PEVSS auprès de 12 cas de CF, 5 frères et sœurs des enfants avec CF et 15 témoins entre 6 mois et 3 ans. Nous montrons une augmentation de la magnitude et de l’alignement de phase des composantes gamma des PEVSS chez les enfants avec CF comparés au groupe témoin et à la fratrie. Ces travaux ont permis d’identifier des phénotypes électro-cliniques d’intérêt qui différencient les enfants avec CF des enfants témoins et de leur fratrie. L’étape suivante sera de vérifier s’il y a une association entre les anomalies retrouvées, la présentation clinique et le pronostic des CF. Cela pourrait éventuellement aider à identifier les enfants à haut risque de développer une épilepsie et permettre l’institution d’un traitement neuroprotecteur précoce.

Les cartes fonctionnelles dans le cortex visuel du chat : nouvelles stratégies d’évaluation en imagerie optique et mise en évidence de l’organisation anatomo-fonctionnelle

Le regroupement des neurones de propriétés similaires est à l’origine de modules permettant d’optimiser l’analyse de l’information. La conséquence est la présence de cartes fonctionnelles dans le cortex visuel primaire de certains mammifères pour de nombreux paramètres tels que l’orientation, la direction du mouvement ou la position des stimuli (visuotopie). Le premier volet de cette thèse est consacré à caractériser l’organisation modulaire dans le cortex visuel primaire pour un paramètre fondamental, la suppression centre / pourtour et au delà du cortex visuel primaire (dans l’aire 21a), pour l’orientation et la direction. Toutes les études ont été effectuées à l’aide de l’imagerie optique des signaux intrinsèques sur le cortex visuel du chat anesthésié. La quantification de la modulation par la taille des stimuli à permis de révéler la présence de modules de forte et de faible suppression par le pourtour dans le cortex visuel primaire (aires 17 et 18). Ce type d’organisation n’avait été observé jusqu’ici que dans une aire de plus haut niveau hiérarchique chez le primate. Une organisation modulaire pour l’orientation, similaire à celle observée dans le cortex visuel primaire a été révélée dans l’aire 21a. Par contre, contrairement à l’aire 18, l’aire 21a ne semblait pas être organisée en domaine de direction. L’ensemble de ces résultats pourront permettre d’alimenter les connaissances sur l’organisation anatomo-fonctionnelle du cortex visuel du chat mais également de mieux comprendre les facteurs qui déterminent la présence d’une organisation modulaire. Le deuxième volet abordé dans cette thèse s’est intéressé à l’amélioration de l’aspect quantitatif apporté par l’analyse temporelle en imagerie optique des signaux intrinsèques. Cette nouvelle approche, basée sur l’analyse de Fourier a permis d’augmenter considérablement le rapport signal / bruit des enregistrements. Toutefois, cette analyse ne s’est basée jusqu’ici que sur la quantification d’une seule harmonique ce qui a limité son emploi à la cartographie de l’orientation et de rétinotopie uniquement. En exploitant les plus hautes harmoniques, un modèle a été proposé afin d’estimer la taille des champs récepteurs et la sélectivité à la direction. Ce modèle a par la suite été validé par des approches conventionnelles dans le cortex visuel primaire.

Apprentissage de représentations musicales à l'aide d'architectures profondes et multiéchelles

L'apprentissage machine (AM) est un outil important dans le domaine de la recherche d'information musicale (Music Information Retrieval ou MIR). De nombreuses tâches de MIR peuvent être résolues en entraînant un classifieur sur un ensemble de caractéristiques. Pour les tâches de MIR se basant sur l'audio musical, il est possible d'extraire de l'audio les caractéristiques pertinentes à l'aide de méthodes traitement de signal. Toutefois, certains aspects musicaux sont difficiles à extraire à l'aide de simples heuristiques. Afin d'obtenir des caractéristiques plus riches, il est possible d'utiliser l'AM pour apprendre une représentation musicale à partir de l'audio. Ces caractéristiques apprises permettent souvent d'améliorer la performance sur une tâche de MIR donnée. Afin d'apprendre des représentations musicales intéressantes, il est important de considérer les aspects particuliers à l'audio musical dans la conception des modèles d'apprentissage. Vu la structure temporelle et spectrale de l'audio musical, les représentations profondes et multiéchelles sont particulièrement bien conçues pour représenter la musique. Cette thèse porte sur l'apprentissage de représentations de l'audio musical. Des modèles profonds et multiéchelles améliorant l'état de l'art pour des tâches telles que la reconnaissance d'instrument, la reconnaissance de genre et l'étiquetage automatique y sont présentés.

The Wolf and the Whale: aesthetic relationships between electroacoustic music and poetry inspired by the Canadian landscape

La version intégrale de cette thèse est disponible uniquement pour consultation individuelle à la Bibliothèque de musique de l’Université de Montréal (www.bib.umontreal.ca/MU).

Theory and numerical integration of subsurface light transport

En synthèse d’images, reproduire les effets complexes de la lumière sur des matériaux transluminescents, tels que la cire, le marbre ou la peau, contribue grandement au réalisme d’une image. Malheureusement, ce réalisme supplémentaire est couteux en temps de calcul. Les modèles basés sur la théorie de la diffusion visent à réduire ce coût en simulant le comportement physique du transport de la lumière sous surfacique tout en imposant des contraintes de variation sur la lumière incidente et sortante. Une composante importante de ces modèles est leur application à évaluer hiérarchiquement l’intégrale numérique de l’illumination sur la surface d’un objet. Cette thèse révise en premier lieu la littérature actuelle sur la simulation réaliste de la transluminescence, avant d’investiguer plus en profondeur leur application et les extensions des modèles de diffusion en synthèse d’images. Ainsi, nous proposons et évaluons une nouvelle technique d’intégration numérique hiérarchique utilisant une nouvelle analyse fréquentielle de la lumière sortante et incidente pour adapter efficacement le taux d’échantillonnage pendant l’intégration. Nous appliquons cette théorie à plusieurs modèles qui correspondent à l’état de l’art en diffusion, octroyant une amélioration possible à leur efficacité et précision.

PSWT Based Linear Predictive Coding and Development of a Parallel Multiple Subsequence Structure for DWT Computation

During 1990's the Wavelet Transform emerged as an important signal processing tool with potential applications in time-frequency analysis and non-stationary signal processing.Wavelets have gained popularity in broad range of disciplines like signal/image compression, medical diagnostics, boundary value problems, geophysical signal processing, statistical signal processing,pattern recognition,underwater acoustics etc.In 1993, G. Evangelista introduced the Pitch- synchronous Wavelet Transform, which is particularly suited for pseudo-periodic signal processing.The work presented in this thesis mainly concentrates on two interrelated topics in signal processing,viz. the Wavelet Transform based signal compression and the computation of Discrete Wavelet Transform. A new compression scheme is described in which the Pitch-Synchronous Wavelet Transform technique is combined with the popular linear Predictive Coding method for pseudo-periodic signal processing. Subsequently,A novel Parallel Multiple Subsequence structure is presented for the efficient computation of Wavelet Transform. Case studies also presented to highlight the potential applications.

Photothermal beam deflection for non-destructive evaluation of semiconductor thin films

Non-destructive testing (NDT) is the use of non-invasive techniques to determine the integrity of a material, component, or structure. Engineers and scientists use NDT in a variety of applications, including medical imaging, materials analysis, and process control.Photothermal beam deflection technique is one of the most promising NDT technologies. Tremendous R&D effort has been made for improving the efficiency and simplicity of this technique. It is a popular technique because it can probe surfaces irrespective of the size of the sample and its surroundings. This technique has been used to characterize several semiconductor materials, because of its non-destructive and non-contact evaluation strategy. Its application further extends to analysis of wide variety of materials. Instrumentation of a NDT technique is very crucial for any material analysis. Chapter two explores the various excitation sources, source modulation techniques, detection and signal processing schemes currently practised. The features of the experimental arrangement including the steps for alignment, automation, data acquisition and data analysis are explained giving due importance to details.Theoretical studies form the backbone of photothermal techniques. The outcome of a theoretical work is the foundation of an application.The reliability of the theoretical model developed and used is proven from the studies done on crystalline.The technique is applied for analysis of transport properties such as thermal diffusivity, mobility, surface recombination velocity and minority carrier life time of the material and thermal imaging of solar cell absorber layer materials like CuInS2, CuInSe2 and SnS thin films.analysis of In2S3 thin films, which are used as buffer layer material in solar cells. The various influences of film composition, chlorine and silver incorporation in this material is brought out from the measurement of transport properties and analysis of sub band gap levels.The application of photothermal deflection technique for characterization of solar cells is a relatively new area that requires considerable attention.The application of photothermal deflection technique for characterization of solar cells is a relatively new area that requires considerable attention. Chapter six thus elucidates the theoretical aspects of application of photothermal techniques for solar cell analysis. The experimental design and method for determination of solar cell efficiency, optimum load resistance and series resistance with results from the analysis of CuInS2/In2S3 based solar cell forms the skeleton of this chapter.

Development of a New Transform:MRT

Fourier transform methods are employed heavily in digital signal processing. Discrete Fourier Transform (DFT) is among the most commonly used digital signal transforms. The exponential kernel of the DFT has the properties of symmetry and periodicity. Fast Fourier Transform (FFT) methods for fast DFT computation exploit these kernel properties in different ways. In this thesis, an approach of grouping data on the basis of the corresponding phase of the exponential kernel of the DFT is exploited to introduce a new digital signal transform, named the M-dimensional Real Transform (MRT), for l-D and 2-D signals. The new transform is developed using number theoretic principles as regards its specific features. A few properties of the transform are explored, and an inverse transform presented. A fundamental assumption is that the size of the input signal be even. The transform computation involves only real additions. The MRT is an integer-to-integer transform. There are two kinds of redundancy, complete redundancy & derived redundancy, in MRT. Redundancy is analyzed and removed to arrive at a more compact version called the Unique MRT (UMRT). l-D UMRT is a non-expansive transform for all signal sizes, while the 2-D UMRT is non-expansive for signal sizes that are powers of 2. The 2-D UMRT is applied in image processing applications like image compression and orientation analysis. The MRT & UMRT, being general transforms, will find potential applications in various fields of signal and image processing.

Development and Evaluation of Blind Identification Techniques for Nonlinear Systems

Identification and Control of Non‐linear dynamical systems are challenging problems to the control engineers.The topic is equally relevant in communication,weather prediction ,bio medical systems and even in social systems,where nonlinearity is an integral part of the system behavior.Most of the real world systems are nonlinear in nature and wide applications are there for nonlinear system identification/modeling.The basic approach in analyzing the nonlinear systems is to build a model from known behavior manifest in the form of system output.The problem of modeling boils down to computing a suitably parameterized model,representing the process.The parameters of the model are adjusted to optimize a performanace function,based on error between the given process output and identified process/model output.While the linear system identification is well established with many classical approaches,most of those methods cannot be directly applied for nonlinear system identification.The problem becomes more complex if the system is completely unknown but only the output time series is available.Blind recognition problem is the direct consequence of such a situation.The thesis concentrates on such problems.Capability of Artificial Neural Networks to approximate many nonlinear input-output maps makes it predominantly suitable for building a function for the identification of nonlinear systems,where only the time series is available.The literature is rich with a variety of algorithms to train the Neural Network model.A comprehensive study of the computation of the model parameters,using the different algorithms and the comparison among them to choose the best technique is still a demanding requirement from practical system designers,which is not available in a concise form in the literature.The thesis is thus an attempt to develop and evaluate some of the well known algorithms and propose some new techniques,in the context of Blind recognition of nonlinear systems.It also attempts to establish the relative merits and demerits of the different approaches.comprehensiveness is achieved in utilizing the benefits of well known evaluation techniques from statistics. The study concludes by providing the results of implementation of the currently available and modified versions and newly introduced techniques for nonlinear blind system modeling followed by a comparison of their performance.It is expected that,such comprehensive study and the comparison process can be of great relevance in many fields including chemical,electrical,biological,financial and weather data analysis.Further the results reported would be of immense help for practical system designers and analysts in selecting the most appropriate method based on the goodness of the model for the particular context.

Decimation Filter Design Toolbox for Multi-Standard Wireless Transceivers using MATLAB.

The demand for new telecommunication services requiring higher capacities, data rates and different operating modes have motivated the development of new generation multi-standard wireless transceivers. A multi-standard design often involves extensive system level analysis and architectural partitioning, typically requiring extensive calculations. In this research, a decimation filter design tool for wireless communication standards consisting of GSM, WCDMA, WLANa, WLANb, WLANg and WiMAX is developed in MATLAB® using GUIDE environment for visual analysis. The user can select a required wireless communication standard, and obtain the corresponding multistage decimation filter implementation using this toolbox. The toolbox helps the user or design engineer to perform a quick design and analysis of decimation filter for multiple standards without doing extensive calculation of the underlying methods.

DNA Sequence Representation methods

DNA sequence representation methods are used to denote a gene structure effectively and help in similarities/dissimilarities analysis of coding sequences. Many different kinds of representations have been proposed in the literature. They can be broadly classified into Numerical, Graphical, Geometrical and Hybrid representation methods. DNA structure and function analysis are made easy with graphical and geometrical representation methods since it gives visual representation of a DNA structure. In numerical method, numerical values are assigned to a sequence and digital signal processing methods are used to analyze the sequence. Hybrid approaches are also reported in the literature to analyze DNA sequences. This paper reviews the latest developments in DNA Sequence representation methods. We also present a taxonomy of various methods. A comparison of these methods where ever possible is also done

A System for Offline Recognition of Handwritten Characters in Malayalam Script

In this paper, we propose a handwritten character recognition system for Malayalam language. The feature extraction phase consists of gradient and curvature calculation and dimensionality reduction using Principal Component Analysis. Directional information from the arc tangent of gradient is used as gradient feature. Strength of gradient in curvature direction is used as the curvature feature. The proposed system uses a combination of gradient and curvature feature in reduced dimension as the feature vector. For classification, discriminative power of Support Vector Machine (SVM) is evaluated. The results reveal that SVM with Radial Basis Function (RBF) kernel yield the best performance with 96.28% and 97.96% of accuracy in two different datasets. This is the highest accuracy ever reported on these datasets

Developing a Child Friendly Text-to-Speech System

This paper discusses the implementation details of a child friendly, good quality, English text-to-speech (TTS) system that is phoneme-based, concatenative, easy to set up and use with little memory. Direct waveform concatenation and linear prediction coding (LPC) are used. Most existing TTS systems are unit-selection based, which use standard speech databases available in neutral adult voices.Here reduced memory is achieved by the concatenation of phonemes and by replacing phonetic wave files with their LPC coefficients. Linguistic analysis was used to reduce the algorithmic complexity instead of signal processing techniques. Sufficient degree of customization and generalization catering to the needs of the child user had been included through the provision for vocabulary and voice selection to suit the requisites of the child. Prosody had also been incorporated. This inexpensive TTS systemwas implemented inMATLAB, with the synthesis presented by means of a graphical user interface (GUI), thus making it child friendly. This can be used not only as an interesting language learning aid for the normal child but it also serves as a speech aid to the vocally disabled child. The quality of the synthesized speech was evaluated using the mean opinion score (MOS).

Feature Point Detection and Curve Approximation for Early Processing of Freehand Sketches

Freehand sketching is both a natural and crucial part of design, yet is unsupported by current design automation software. We are working to combine the flexibility and ease of use of paper and pencil with the processing power of a computer to produce a design environment that feels as natural as paper, yet is considerably smarter. One of the most basic steps in accomplishing this is converting the original digitized pen strokes in the sketch into the intended geometric objects using feature point detection and approximation. We demonstrate how multiple sources of information can be combined for feature detection in strokes and apply this technique using two approaches to signal processing, one using simple average based thresholding and a second using scale space.