Les applications de gestion de flux sont responsables de la majorité des calculs des systèmes embarqués (vidéo conférence, vision par ordinateur). Leurs exigences de haute performance rendent leur mise en œuvre parallèle nécessaire. Par conséquent, il est de plus en plus courant que les systèmes embarqués modernes incluent des processeurs multi-cœurs qui permettent un parallélisme massif. La mise en œuvre des applications de gestion de flux sur des multi-cœurs est difficile à cause de leur complexité, qui tend à augmenter, et de leurs exigences strictes à la fois qualitatives (robustesse, fiabilité) et quantitatives (débit, consommation d'énergie). Ceci est observé dans l'évolution de codecs vidéo qui ne cessent d'augmenter en complexité, tandis que leurs exigences de performance demeurent les mêmes. Les modèles de calcul (MdC) flot de données ont été développés pour faciliter la conception de ces applications qui sont typiquement composées de filtres qui échangent des flux de données via des liens de communication. Ces modèles fournissent une représentation intuitive des applications de gestion de flux, tout en exposant le parallélisme de tâches de l'application. En outre, ils fournissent des analyses statiques pour la vivacité et l'exécution en mémoire bornée. Cependant, les applications de gestion de flux modernes comportent des filtres qui échangent des quantités de données variables, et des liens de communication qui peuvent être activés / désactivés. Dans cette thèse, nous présentons un nouveau MdC flot de données, le Boolean Parametric Data Flow (BPDF), qui permet le paramétrage de la quantité de données échangées entre les filtres en utilisant des paramètres entiers et l'activation et la désactivation de liens de communication en utilisant des paramètres booléens. De cette manière, BPDF est capable de exprimer des applications plus complexes, comme les décodeurs vidéo modernes. Malgré l'augmentation de l'expressivité, les applications BPDF restent statiquement analysables pour la vivacité et l'exécution en mémoire bornée. Cependant, l'expressivité accrue complique grandement la mise en œuvre. Les paramètres entiers entraînent des dépendances de données de type paramétrique et les paramètres booléens peuvent désactiver des liens de communication et ainsi éliminer des dépendances de données. Pour cette raison, nous proposons un cadre d'ordonnancement qui produit des ordonnancements de type ``aussi tôt que possible'' (ASAP) pour un placement statique donné. Il utilise des contraintes d'ordonnancement, soit issues de l'application (dépendance de données) ou de l'utilisateur (optimisations d'ordonnancement). Les contraintes sont analysées pour la vivacité et, si possible, simplifiées. De cette façon, notre cadre permet une grande variété de politiques d'ordonnancement, tout en garantissant la vivacité de l'application. Enfin, le calcul du débit d'une application est important tant avant que pendant l'exécution. Il permet de vérifier que l'application satisfait ses exigences de performance et il permet de prendre des décisions d'ordonnancement à l'exécution qui peuvent améliorer la performance ou la consommation d'énergie. Nous traitons ce problème en trouvant des expressions paramétriques pour le débit maximum d'un sous-ensemble de BPDF. Enfin, nous proposons un algorithme qui calcule une taille des buffers suffisante pour que l'application BPDF ait un débit maximum. / Streaming applications are responsible for the majority of the computation load in many embedded systems (video conferencing, computer vision etc). Their high performance requirements make parallel implementations a necessity. Hence, more and more modern embedded systems include many-core processors that allow massive parallelism. Parallel implementation of streaming applications on many-core platforms is challenging because of their complexity, which tends to increase, and their strict requirements both qualitative (e.g., robustness, reliability) and quantitative (e.g., throughput, power consumption). This is observed in the evolution of video codecs that keep increasing in complexity, while their performance requirements remain the same or even increase. Data flow models of computation (MoCs) have been developed to facilitate the design process of such applications, which are typically composed of filters exchanging streams of data via communication links. Data flow MoCs provide an intuitive representation of streaming applications, while exposing the available parallelism of the application. Moreover, they provide static analyses for liveness and boundedness. However, modern streaming applications feature filters that exchange variable amounts of data, and communication links that are not always active. In this thesis, we present a new data flow MoC, the Boolean Parametric Data Flow (BPDF), that allows parametrization of the amount of data exchanged between the filters using integer parameters and the enabling and disabling of communication links using boolean parameters. In this way, BPDF is able to capture more complex streaming applications, like video decoders. Despite the increase in expressiveness, BPDF applications remain statically analyzable for liveness and boundedness. However, increased expressiveness greatly complicates implementation. Integer parameters result in parametric data dependencies and the boolean parameters disable communication links, effectively removing data dependencies. We propose a scheduling framework that facilitates the scheduling of BPDF applications. Our scheduling framework produces as soon as possible schedules for a given static mapping. It takes us input scheduling constraints that derive either from the application (data dependencies) or from the user (schedule optimizations). The constraints are analyzed for liveness and, if possible, simplified. In this way, our framework provides flexibility, while guaranteeing the liveness of the application. Finally, calculation of the throughput of an application is important both at compile-time and at run-time. It allows to verify at compile-time that the application meets its performance requirements and it allows to take scheduling decisions at run-time that can improve performance or power consumption. We approach this problem by finding parametric throughput expressions for the maximum throughput of a subset of BPDF graphs. Finally, we provide an algorithm that calculates sufficient buffer sizes for the BPDF graph to operate at maximum throughput.

Advanced digital signal processing systems require specialized high-performance embedded computer architectures. The term high-performance translates to large amounts of data and computations per time unit. The term embedded further implies requirements on physical size and power efficiency. Thus the requirements are of both functional and non-functional nature. This thesis addresses the development of high-performance digital signal processing systems relying on manycore technology. We propose building two-level hierarchical computer architectures for this domain of applications. Further, we outline a tool flow based on methods and analysis techniques for automated, multi-objective mapping of such applications on distributed memory manycore processors. In particular, the focus is put on how to provide a means for tunable strategies for mapping of task graphs on array structured distributed memory manycores, with respect to given application constraints. We argue for code mapping strategies based on predicted execution performance, which can be used in an auto-tuning feedback loop or to guide manual tuning directed by the programmer. Automated parallelization, optimisation and mapping to a manycore processor benefits from the use of a concurrent programming model as the starting point. Such a model allows the programmer to express different types and granularities of parallelism as well as computation characteristics of importance in the addressed class of applications. The programming model should also abstract away machine dependent hardware details. The analytical study of WCDMA baseband processing in radio base stations, presented in this thesis, suggests dataflow models as a good match to the characteristics of the application and as execution model abstracting computations on a manycore. Construction of portable tools further requires a manycore machine model and an intermediate representation. The models are needed in order to decouple algorithms, used to transform and map application software, from hardware. We propose a manycore machine model that captures common hardware resources, as well as resource dependent performance metrics for parallel computation and communication. Further, we have developed a multifunctional intermediate representation, which can be used as source for code generation and for dynamic execution analysis. Finally, we demonstrate how we can dynamically analyse execution using abstract interpretation on the intermediate representation. It is shown that the performance predictions can be used to accurately rank different mappings by best throughput or shortest end-to-end computation latency.

Many small enterprises in Lithuania don’t use information systems in their accounting. This is because almost all of already developed accounting software is quite complex, expensive and has many additional features, witch aren’t useful for a small enterprises. This is why it has been decided to develop own specific software for a goods accounting. User interface and data structure should be adapted to the specific functions of the small optical enterprise. The purposes of the developed information system are to increase work and accounting quality, to decrease time needed for accounting, to avoid saving redundant information, to automate and simplify the process of creating analytical reports, to avoid mistakes in accounting and make accounting more efficient. In the process of developing this information system there was analyzed functional and nonfunctional, manage mental and common requirement issues. The models of dataflow, data structure, and applications were used in the requirement specification. Architecture of components and software structure is also provided in this project. The realization of this project was accomplished by means of Microsoft Access 2000. There was created database, graphical user interface, and integrated Microsoft Visual Basic for Applications was used to perform programming tasks. Abilities of this software are fully sufficient for these tasks. Selected design techniques and tools had proved themselves in solving software for small... [to full text]

Une des questions centrales de la vision informatique est celle de la conception et apprentissage de représentations du monde visuel. Quel type de représentation peut permettre à un système de vision artificielle de détecter et classifier les objects en catégories, indépendamment de leur pose, échelle, illumination, et obstruction. Plus intéressant encore, comment est-ce qu'un tel système peut apprendre cette représentation de façon automatisée, de la même manière que les animaux et humains parviennent à émerger une représentation du monde qui les entoure. Une question liée est celle de la faisabilité calculatoire, et plus précisément celle de l'efficacité calculatoire. Étant donné un modèle visuel, avec quelle efficacité peut-il être entrainé, et appliqué à de nouvelles données sensorielles. Cette efficacité a plusieurs dimensions: l'énergie consommée, la vitesse de calcul, et l'utilisation mémoire. Dans cette thèse je présente trois contributions à la vision informatique: (1) une nouvelle architecture de réseau convolutif profond multi-échelle, permettant de capturer des relations longue distance entre variables d'entrée dans des données type image, (2) un algorithme à base d'arbres permettant d'explorer de multiples candidats de segmentation, pour produire une segmentation sémantique avec confiance maximale, (3) une architecture de processeur dataflow optimisée pour le calcul de réseaux convolutifs profonds. Ces trois contributions ont été produites dans le but d'améliorer l'état de l'art dans le domain de l'analyse sémantique des images, avec une emphase sur l'efficacité calculatoire. L'analyse de scènes (scene parsing) consiste à étiqueter chaque pixel d'une image avec la catégorie de l'objet auquel il appartient. Dans la première partie de cette thèse, je propose une méthode qui utilise un réseau convolutif profond, entrainé à même les pixels, pour extraire des vecteurs de caractéristiques (features) qui encodent des régions de plusieurs résolutions, centrées sur chaque pixel. Cette méthode permet d'éviter l'usage de caractéristiques créées manuellement. Ces caractéristiques étant multi-échelle, elles permettent au modèle de capturer des relations locales et globales à la scène. En parallèle, un arbre de composants de segmentation est calculé à partir de graphe de dis-similarité des pixels. Les vecteurs de caractéristiques associés à chaque noeud de l'arbre sont agrégés, et utilisés pour entrainé un estimateur de la distribution des catégories d'objets présents dans ce segment. Un sous-ensemble des noeuds de l'arbre, couvrant l'image, est ensuite sélectionné de façon à maximiser la pureté moyenne des distributions de classes. En maximisant cette pureté, la probabilité que chaque composant ne contienne qu'un objet est maximisée. Le système global produit une précision record sur plusieurs benchmarks publics. Le calcul de réseaux convolutifs profonds ne dépend que de quelques opérateurs de base, qui sont particulièrement adaptés à une implémentation hardware dédiée. Dans la deuxième partie de cette thèse, je présente une architecture de processeur dataflow dédiée et optimisée pour le calcul de systèmes de vision à base de réseaux convolutifs--neuFlow--et un compilateur--luaFlow--dont le rôle est de compiler une description haut-niveau (type graphe) de réseaux convolutifs pour produire un flot de données et calculs optimal pour l'architecture. Ce système a été développé pour faire de la détection, catégorisation et localisation d'objets en temps réel, dans des scènes complexes, en ne consommant que 10 Watts, avec une implémentation FPGA standard.

The ever-increasing functional and nonfunctional requirements in real-time safety-critical embedded systems call for new design flows that solve the specification, validation, and synthesis problems. Ensuring key properties, such as functional determinism and temporal predictability, has been the main objective of many embedded system design models. Dataflow models of computation (such as KPN, SDF, CSDF, etc.) are widely used to model stream-based embedded systems due to their inherent functional determinism. Since the introduction of the (C)SDF model, a considerable effort has been made to solve the static-periodic scheduling problem. Ensuring boundedness and liveness is the essence of the proposed algorithms in addition to optimizing some nonfunctional performance metrics (e.g. buffer minimization, throughput maximization, etc.). However, nowadays real-time embedded systems are so complex that real-time operating systems are used to manage hardware resources and host real-time tasks. Most of real-time operating systems rely on priority-driven scheduling algorithms (e.g. RM, EDF, etc.) instead of static schedules which are inflexible and difficult to maintain. This thesis addresses the real-time scheduling problem of dataflow graph specifications; i.e. transformation of the dataflow specification to a set of independent real-time tasks w.r.t. a given priority-driven scheduling policy such that the following properties are satisfied: (1) channels are bounded and overflow/underflow-free; (2) the task set is schedulable on a given uniprocessor (or multiprocessor) architecture. This problem requires the synthesis of scheduling parameters (e.g. periods, priorities, processor allocation, etc.) and channel capacities. Furthermore, the thesis considers two performance optimization problems: buffer minimization and throughput maximization.

Les langages synchrones sont apparus autour des années quatre-vingt, en réponse à un besoin d’avoir un modèle mathématique simple pour implémenter des systèmes temps réel critiques. Dans ce modèle, le temps est découpé en instants discrets durant lesquels tous les composants du système reçoivent et produisent une donnée. Cette modélisation permet des raisonnements beaucoup plus simples en évitant de devoir prendre en compte le temps de calcul de chaque opération. Dans le monde du logiciel critique, la fiabilité du matériel et de son fonctionnement sont primordiaux, et on accepte d’être plus lent si on devient plus sûr. Afin d’augmenter cette fiabilité, plutôt que de concevoir manuellement tout le système, on utilise des machines qui synthétisent automatiquement le système souhaité à partir d’une description la plus concise possible. Dans le cas du logiciel, ce mécanisme s’appelle la compilation, et évite des erreurs introduites par l’homme par inadvertance. Elle ne garantit cependant pas la bonne correspondance entre le système produit et la description donnée. Des travaux récents menés par une équipe INRIA dirigée par Xavier Leroy ont abouti en 2008 au compilateur CompCert d’un sous-ensemble large de C vers l’assembleur PowerPC pour lequel il a été prouvé dans l’assistant de preuve Coq que le code assembleur produit correspond bien à la description en C du programme source. Un tel compilateur offre des garanties fortes de bonne correspondance entre le système synthétisé et la description donnée. De plus, avec les compilateurs utilisés pour le temps réel critique, la plupart des optimisations sont désactivées afin d’éviter les erreurs qui y sont liées. Dans CompCert, des optimisations elles aussi prouvées sont proposées, ce qui pourrait permettre ces passes dans la production de systèmes temps réel critiques sans en compromettre la fiabilité. Le but de cette thèse est d’avoir une approche similaire mais spécifique à un langage synchrone, donc plus approprié à la description de systèmes temps réel critiques que ne l’est le C. Un langage synchrone flots de données semblable à Lustre, nommé Ls, et un langage impératif semblable au langage C, nommé Obc y sont proposés ainsi que leur sémantique formelle et une chaîne de compilation avec des preuves de préservation de sémantique le long de cette chaîne. / Synchronous languages first appeared during the 80’s, in order to provide a mathematical model for safety-critical systems. In this model, time is discrete. At each instant, all components of the system simultaneously receive and produce some data. This model allows simpler reasonning on the behaviour of the system, as it does not involve the time required for each of the operations for every component. In safety-critical systems, safety is the rule, so a poor performance behaviour can be allowed if it improves safety. In order to improve safety, rather than conceiving directly the system, machines are used to automatically design the system from a given concise description. In the case of software, this machine is called a compiler, and avoids issues due to some human inadvertence. But it does not ensure that the produced system and the description specification really show the same behaviour. Some recent work from an INRIA team lead by Xavier Leroy achieved in 2008 the realisation of the CompCert compiler from a large subset of C to PowerPC assembly, for which it was proven inside of the Coq proof assistant that the produced system fits its source description. Such a compiler offers strong guarantees that the produced system and its given description by the programmer really fit. Furthermore, most current compiler’s optimizations are disabled when dealing with safety-critical systems in order to avoid tedious compilation errors that optimizations may introduce. Proofs for optimizations may allow their use in this domain without affecting the faith we could place in the compiler. The aim of this thesis is to follow a similar path, but this one on a language which would be more suited for safety-critical systems than the C programming language. Some dataflow synchronous programming language very similar to Lustre, called Ls is described with its formal semantics, as well as an imperative programming language similar to a subset of C called Obc. Furthermore some compilation process is described as well as some proofs that the semantics is preserved during the compilation process.

Les applications de gestion de flux sont responsables de la majorité des calculs des systèmes embarqués (vidéo conférence, vision par ordinateur). Leurs exigences de haute performance rendent leur mise en œuvre parallèle nécessaire. Par conséquent, il est de plus en plus courant que les systèmes embarqués modernes incluent des processeurs multi-cœurs qui permettent un parallélisme massif. La mise en œuvre des applications de gestion de flux sur des multi-cœurs est difficile à cause de leur complexité, qui tend à augmenter, et de leurs exigences strictes à la fois qualitatives (robustesse, fiabilité) et quantitatives (débit, consommation d'énergie). Ceci est observé dans l'évolution de codecs vidéo qui ne cessent d'augmenter en complexité, tandis que leurs exigences de performance demeurent les mêmes. Les modèles de calcul (MdC) flot de données ont été développés pour faciliter la conception de ces applications qui sont typiquement composées de filtres qui échangent des flux de données via des liens de communication. Ces modèles fournissent une représentation intuitive des applications de gestion de flux, tout en exposant le parallélisme de tâches de l'application. En outre, ils fournissent des analyses statiques pour la vivacité et l'exécution en mémoire bornée. Cependant, les applications de gestion de flux modernes comportent des filtres qui échangent des quantités de données variables, et des liens de communication qui peuvent être activés / désactivés. Dans cette thèse, nous présentons un nouveau MdC flot de données, le Boolean Parametric Data Flow (BPDF), qui permet le paramétrage de la quantité de données échangées entre les filtres en utilisant des paramètres entiers et l'activation et la désactivation de liens de communication en utilisant des paramètres booléens. De cette manière, BPDF est capable de exprimer des applications plus complexes, comme les décodeurs vidéo modernes. Malgré l'augmentation de l'expressivité, les applications BPDF restent statiquement analysables pour la vivacité et l'exécution en mémoire bornée. Cependant, l'expressivité accrue complique grandement la mise en œuvre. Les paramètres entiers entraînent des dépendances de données de type paramétrique et les paramètres booléens peuvent désactiver des liens de communication et ainsi éliminer des dépendances de données. Pour cette raison, nous proposons un cadre d'ordonnancement qui produit des ordonnancements de type ``aussi tôt que possible'' (ASAP) pour un placement statique donné. Il utilise des contraintes d'ordonnancement, soit issues de l'application (dépendance de données) ou de l'utilisateur (optimisations d'ordonnancement). Les contraintes sont analysées pour la vivacité et, si possible, simplifiées. De cette façon, notre cadre permet une grande variété de politiques d'ordonnancement, tout en garantissant la vivacité de l'application. Enfin, le calcul du débit d'une application est important tant avant que pendant l'exécution. Il permet de vérifier que l'application satisfait ses exigences de performance et il permet de prendre des décisions d'ordonnancement à l'exécution qui peuvent améliorer la performance ou la consommation d'énergie. Nous traitons ce problème en trouvant des expressions paramétriques pour le débit maximum d'un sous-ensemble de BPDF. Enfin, nous proposons un algorithme qui calcule une taille des buffers suffisante pour que l'application BPDF ait un débit maximum. / Streaming applications are responsible for the majority of the computation load in many embedded systems (video conferencing, computer vision etc). Their high performance requirements make parallel implementations a necessity. Hence, more and more modern embedded systems include many-core processors that allow massive parallelism. Parallel implementation of streaming applications on many-core platforms is challenging because of their complexity, which tends to increase, and their strict requirements both qualitative (e.g., robustness, reliability) and quantitative (e.g., throughput, power consumption). This is observed in the evolution of video codecs that keep increasing in complexity, while their performance requirements remain the same or even increase. Data flow models of computation (MoCs) have been developed to facilitate the design process of such applications, which are typically composed of filters exchanging streams of data via communication links. Data flow MoCs provide an intuitive representation of streaming applications, while exposing the available parallelism of the application. Moreover, they provide static analyses for liveness and boundedness. However, modern streaming applications feature filters that exchange variable amounts of data, and communication links that are not always active. In this thesis, we present a new data flow MoC, the Boolean Parametric Data Flow (BPDF), that allows parametrization of the amount of data exchanged between the filters using integer parameters and the enabling and disabling of communication links using boolean parameters. In this way, BPDF is able to capture more complex streaming applications, like video decoders. Despite the increase in expressiveness, BPDF applications remain statically analyzable for liveness and boundedness. However, increased expressiveness greatly complicates implementation. Integer parameters result in parametric data dependencies and the boolean parameters disable communication links, effectively removing data dependencies. We propose a scheduling framework that facilitates the scheduling of BPDF applications. Our scheduling framework produces as soon as possible schedules for a given static mapping. It takes us input scheduling constraints that derive either from the application (data dependencies) or from the user (schedule optimizations). The constraints are analyzed for liveness and, if possible, simplified. In this way, our framework provides flexibility, while guaranteeing the liveness of the application. Finally, calculation of the throughput of an application is important both at compile-time and at run-time. It allows to verify at compile-time that the application meets its performance requirements and it allows to take scheduling decisions at run-time that can improve performance or power consumption. We approach this problem by finding parametric throughput expressions for the maximum throughput of a subset of BPDF graphs. Finally, we provide an algorithm that calculates sufficient buffer sizes for the BPDF graph to operate at maximum throughput.

Les décompositions en matrices triangulaires sont une brique de base fondamentale en calcul algébrique. Ils sont utilisés pour résoudre des systèmes linéaires et calculer le rang, le déterminant, l'espace nul ou les profiles de rang en ligne et en colonne d'une matrix. Le projet de cette thèse est de développer des implantations hautes performances parallèles de l'élimination de Gauss exact sur des machines à mémoire partagée.Dans le but d'abstraire le code de l'environnement de calcul parallèle utilisé, un langage dédié PALADIn (Parallel Algebraic Linear Algebra Dedicated Interface) a été implanté et est basé essentiellement sur des macros C/C++. Ce langage permet à l'utilisateur d'écrire un code C++ et tirer partie d’exécutions séquentielles et parallèles sur des architectures à mémoires partagées en utilisant le standard OpenMP et les environnements parallel KAAPI et TBB, ce qui lui permet de bénéficier d'un parallélisme de données et de taches.Plusieurs aspects de l'algèbre linéaire exacte parallèle ont été étudiés. Nous avons construit de façon incrémentale des noyaux parallèles efficaces pour les multiplication de matrice, la résolution de systèmes triangulaires au dessus duquel plusieurs variantes de l'algorithme de décomposition PLUQ sont construites. Nous étudions la parallélisation de ces noyaux en utilisant plusieurs variantes algorithmiques itératives ou récursives et en utilisant des stratégies de découpes variées.Nous proposons un nouvel algorithme récursive de l'élimination de Gauss qui peut calculer simultanément les profiles de rang en ligne et en colonne d'une matrice et de toutes ses sous-matrices principales, tout en étant un algorithme état de l'art de l'élimination de Gauss. Nous étudions aussi les conditions pour qu'un algorithme de l'élimination de Gauss révèle cette information en définissant un nouvel invariant matriciel, la matrice de profil de rang. / Triangular matrix decompositions are fundamental building blocks in computational linear algebra. They are used to solve linear systems, compute the rank, the determinant, the null-space or the row and column rank profiles of a matrix. The project of my PhD thesis is to develop high performance shared memory parallel implementations of exact Gaussian elimination.In order to abstract the computational code from the parallel programming environment, we developed a domain specific language, PALADIn: Parallel Algebraic Linear Algebra Dedicated Interface, that is based on C/C + + macros. This domain specific language allows the user to write C + + code and benefit from sequential and parallel executions on shared memory architectures using the standard OpenMP, TBB and Kaapi parallel runtime systems and thus providing data and task parallelism.Several aspects of parallel exact linear algebra were studied. We incrementally build efficient parallel kernels, for matrix multiplication, triangular system solving, on top of which several variants of PLUQ decomposition algorithm are built. We study the parallelization of these kernels using several algorithmic variants: either iterative or recursive and using different splitting strategies.We propose a recursive Gaussian elimination that can compute simultaneously therow and column rank profiles of a matrix as well as those of all of its leading submatrices, in the same time as state of the art Gaussian elimination algorithms. We also study the conditions making a Gaussian elimination algorithm reveal this information by defining a new matrix invariant, the rank profile matrix.

A definição de requisitos tem sido reconhecida como uma das mais críticas e difíceis tarefas em engenharia de software. A necessidade de ferramentas de suporte é essencial. Nos dias de hoje, entre os vários métodos existentes para apoiar a fase de requisitos, destaca-se o SADT (Structured Analysis and Design Techniques) devido a sua capacidade de representar modelos. Este trabalho estabelece semântica para o método SADT, baseando-se na inter-relação do método aos sistemas de fluxo de dados (redes, grafos e máquinas de fluxo). Faz-se, inicialmente, uma abordagem operacional para a semântica de seus construtos básicos e, posteriormente discute-se a possibilidade de executar especificações através de simulação. Uma ferramenta para suportar o método SADT foi projetada e construída e é apresentada. Ela foi definida a partir de um modelo, denotado por uma classe, através de uma sintaxe abstrata. Essa ferramenta foi implementada no ambiente PROSOFT, fornecendo para o usuário mais de quarenta operações de apoio a construção/manipulação de diagramas. O trabalho também apresenta a especificação formal em VDM - Vienna Development Method, da semântica dos principais construtos do método SADT, bem como uma proposição de execução de especificações através de simulação são ainda indicadas direções nas quais o trabalho pode ser estendido. / The definition of systems requirements has been known as one of the most critical and dificult tasks as far as the software engineering is concerned. The need support is essential. Nowadays, among the various methods devised to support the phase of requirements, a special emphasis is given to the SADT method (Structured Analysis and Design Techniques), due to its capability of representing models. This work set semantic for the SADT method, based primarily upon the interrelation of the method to the systems of dataflow (nets, graphs and dataflow machines). It deals with an approach of operational semantics to its basic constructs, and it will, afterwards, discuss the possibility of carry out specifications by simulation. A tool was built to support the SADT method, and it was defined by a model denoted by a class, through an abstract syntax. This tool was implemented in the PROSOFT environment, providing for the user, more than forty support operations for the construction /manipulation of diagrams. This work also presents the formal specification of the semantics of the main constructs of the SADT method in VDM - Vienna Development Method; as well as an execution proposal of specifications through simulation. Directions have been indicated concerning the extension of the research.

A definição de requisitos tem sido reconhecida como uma das mais críticas e difíceis tarefas em engenharia de software. A necessidade de ferramentas de suporte é essencial. Nos dias de hoje, entre os vários métodos existentes para apoiar a fase de requisitos, destaca-se o SADT (Structured Analysis and Design Techniques) devido a sua capacidade de representar modelos. Este trabalho estabelece semântica para o método SADT, baseando-se na inter-relação do método aos sistemas de fluxo de dados (redes, grafos e máquinas de fluxo). Faz-se, inicialmente, uma abordagem operacional para a semântica de seus construtos básicos e, posteriormente discute-se a possibilidade de executar especificações através de simulação. Uma ferramenta para suportar o método SADT foi projetada e construída e é apresentada. Ela foi definida a partir de um modelo, denotado por uma classe, através de uma sintaxe abstrata. Essa ferramenta foi implementada no ambiente PROSOFT, fornecendo para o usuário mais de quarenta operações de apoio a construção/manipulação de diagramas. O trabalho também apresenta a especificação formal em VDM - Vienna Development Method, da semântica dos principais construtos do método SADT, bem como uma proposição de execução de especificações através de simulação são ainda indicadas direções nas quais o trabalho pode ser estendido. / The definition of systems requirements has been known as one of the most critical and dificult tasks as far as the software engineering is concerned. The need support is essential. Nowadays, among the various methods devised to support the phase of requirements, a special emphasis is given to the SADT method (Structured Analysis and Design Techniques), due to its capability of representing models. This work set semantic for the SADT method, based primarily upon the interrelation of the method to the systems of dataflow (nets, graphs and dataflow machines). It deals with an approach of operational semantics to its basic constructs, and it will, afterwards, discuss the possibility of carry out specifications by simulation. A tool was built to support the SADT method, and it was defined by a model denoted by a class, through an abstract syntax. This tool was implemented in the PROSOFT environment, providing for the user, more than forty support operations for the construction /manipulation of diagrams. This work also presents the formal specification of the semantics of the main constructs of the SADT method in VDM - Vienna Development Method; as well as an execution proposal of specifications through simulation. Directions have been indicated concerning the extension of the research.