949 resultados para Parallel programming (computer)
Resumo:
Lvolution rcente des commutateurs de slection de longueurs donde (WSS -Wavelength Selective Switch) favorise le dveloppement du multiplexeur optique dinsertionextraction reconfigurable (ROADM - Reconfigurable Optical Add/Drop Multiplexers) plusieurs degrs sans orientation ni coloration, considr comme un quipement fort prometteur pour les rseaux maills du futur relativement au multiplexage en longueur donde (WDM -Wavelength Division Multiplexing ). Cependant, leur proprit de commutation asymtrique complique la question de lacheminement et de lattribution des longueur dondes (RWA - Routing andWavelength Assignment). Or la plupart des algorithmes de RWA existants ne tiennent pas compte de cette proprit dasymtrie. Linterruption des services cause par des dfauts dquipements sur les chemins optiques (rsultat provenant de la rsolution du problme RWA) a pour consquence la perte dune grande quantit de donnes. Les recherches deviennent ainsi incontournables afin dassurer la survie fonctionnelle des rseaux optiques, savoir, le maintien des services, en particulier en cas de pannes dquipement. La plupart des publications antrieures portaient particulirement sur lutilisation dun systme de protection permettant de garantir le reroutage du trafic en cas dun dfaut dun lien. Cependant, la conception de la protection contre le dfaut dun lien ne savre pas toujours suffisante en termes de survie des rseaux WDM partir de nombreux cas des autres types de pannes devenant courant de nos jours, tels que les bris dquipements, les pannes de deux ou trois liens, etc. En outre, il y a des dfis considrables pour protger les grands rseaux optiques multidomaines composs de rseaux associs un domaine simple, interconnects par des liens interdomaines, o les dtails topologiques internes dun domaine ne sont gnralement pas partags lextrieur. La prsente thse a pour objectif de proposer des modles doptimisation de grande taille et des solutions aux problmes mentionns ci-dessus. Ces modles-ci permettent de gnrer des solutions optimales ou quasi-optimales avec des carts doptimalit mathmatiquement prouve. Pour ce faire, nous avons recours la technique de gnration de colonnes afin de rsoudre les problmes inhrents la programmation linaire de grande envergure. Concernant la question de lapprovisionnement dans les rseaux optiques, nous proposons un nouveau modle de programmation linaire en nombres entiers (ILP - Integer Linear Programming) au problme RWA afin de maximiser le nombre de requtes acceptes (GoS - Grade of Service). Le modle rsultant constitue celui de loptimisation dun ILP de grande taille, ce qui permet dobtenir la solution exacte des instances RWA assez grandes, en supposant que tous les noeuds soient asymtriques et accompagns dune matrice de connectivit de commutation donne. Ensuite, nous modifions le modle et proposons une solution au problme RWA afin de trouver la meilleure matrice de commutation pour un nombre donn de ports et de connexions de commutation, tout en satisfaisant/maximisant la qualit dcoulement du trafic GoS. Relativement la protection des rseaux dun domaine simple, nous proposons des solutions favorisant la protection contre les pannes multiples. En effet, nous dveloppons la protection dun rseau dun domaine simple contre des pannes multiples, en utilisant les p-cycles de protection avec un chemin indpendant des pannes (FIPP - Failure Independent Path Protecting) et de la protection avec un chemin dpendant des pannes (FDPP - Failure Dependent Path-Protecting). Nous proposons ensuite une nouvelle formulation en termes de modles de flots pour les p-cycles FDPP soumis des pannes multiples. Le nouveau modle soulve un problme de taille, qui a un nombre exponentiel de contraintes en raison de certaines contraintes dlimination de sous-tour. Par consquent, afin de rsoudre efficacement ce problme, on examine : (i) une dcomposition hirarchique du problme auxiliaire dans le modle de dcomposition, (ii) des heuristiques pour grer efficacement le grand nombre de contraintes. propos de la protection dans les rseaux multidomaines, nous proposons des systmes de protection contre les pannes dun lien. Tout dabord, un modle doptimisation est propos pour un systme de protection centralise, en supposant que la gestion du rseau soit au courant de tous les dtails des topologies physiques des domaines. Nous proposons ensuite un modle distribu de loptimisation de la protection dans les rseaux optiques multidomaines, une formulation beaucoup plus raliste car elle est base sur lhypothse dune gestion de rseau distribu. Ensuite, nous ajoutons une bande pasiv sante partage afin de rduire le cot de la protection. Plus prcisment, la bande passante de chaque lien intra-domaine est partage entre les p-cycles FIPP et les p-cycles dans une premire tude, puis entre les chemins pour lien/chemin de protection dans une deuxime tude. Enfin, nous recommandons des stratgies parallles aux solutions de grands rseaux optiques multidomaines. Les rsultats de ltude permettent dlaborer une conception efficace dun systme de protection pour un trs large rseau multidomaine (45 domaines), le plus large examin dans la littrature, avec un systme la fois centralis et distribu.
Resumo:
clRNG et clProbdist sont deux interfaces de programmation (APIs) que nous avons dveloppes pour la gnration de nombres alatoires uniformes et non uniformes sur des dispositifs de calculs parallles en utilisant lenvironnement OpenCL. La premire interface permet de crer au niveau dun ordinateur central (hte) des objets de type stream considrs comme des gnrateurs virtuels parallles qui peuvent tre utiliss aussi bien sur lhte que sur les dispositifs parallles (units de traitement graphique, CPU multinoyaux, etc.) pour la gnration de squences de nombres alatoires. La seconde interface permet aussi de gnrer au niveau de ces units des variables alatoires selon diffrentes lois de probabilit continues et discrtes. Dans ce mmoire, nous allons rappeler des notions de base sur les gnrateurs de nombres alatoires, dcrire les systmes htrognes ainsi que les techniques de gnration parallle de nombres alatoires. Nous prsenterons aussi les diffrents modles composant larchitecture de lenvironnement OpenCL et dtaillerons les structures des APIs dveloppes. Nous distinguons pour clRNG les fonctions qui permettent la cration des streams, les fonctions qui gnrent les variables alatoires uniformes ainsi que celles qui manipulent les tats des streams. clProbDist contient les fonctions de gnration de variables alatoires non uniformes selon la technique dinversion ainsi que les fonctions qui permettent de retourner diffrentes statistiques des lois de distribution implmentes. Nous valuerons ces interfaces de programmation avec deux simulations qui implmentent un exemple simplifi dun modle dinventaire et un exemple dune option financire. Enfin, nous fournirons les rsultats dexprimentation sur les performances des gnrateurs implments.
Resumo:
This paper describes JERIM-320, a new 320-bit hash function used for ensuring message integrity and details a comparison with popular hash functions of similar design. JERIM-320 and FORK -256 operate on four parallel lines of message processing while RIPEMD-320 operates on two parallel lines. Popular hash functions like MD5 and SHA-1 use serial successive iteration for designing compression functions and hence are less secure. The parallel branches help JERIM-320 to achieve higher level of security using multiple iterations and processing on the message blocks. The focus of this work is to prove the ability of JERIM 320 in ensuring the integrity of messages to a higher degree to suit the fast growing internet applications
Resumo:
Genetic programming is known to provide good solutions for many problems like the evolution of network protocols and distributed algorithms. In such cases it is most likely a hardwired module of a design framework that assists the engineer to optimize specific aspects of the system to be developed. It provides its results in a fixed format through an internal interface. In this paper we show how the utility of genetic programming can be increased remarkably by isolating it as a component and integrating it into the model-driven software development process. Our genetic programming framework produces XMI-encoded UML models that can easily be loaded into widely available modeling tools which in turn posses code generation as well as additional analysis and test capabilities. We use the evolution of a distributed election algorithm as an example to illustrate how genetic programming can be combined with model-driven development. This example clearly illustrates the advantages of our approach the generation of source code in different programming languages.
Resumo:
This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.
Resumo:
Heutzutage haben selbst durchschnittliche Computersysteme mehrere unabhngige Recheneinheiten (Kerne). Wird ein rechenintensives Problem in mehrere Teilberechnungen unterteilt, knnen diese parallel und damit schneller verarbeitet werden. Obwohl die Entwicklung paralleler Programme mittels Abstraktionen vereinfacht werden kann, ist es selbst fr Experten anspruchsvoll, effiziente und korrekte Programme zu schreiben. Whrend traditionelle Programmiersprachen auf einem eher geringen Abstraktionsniveau arbeiten, bieten funktionale Programmiersprachen wie z.B. Haskell, Mglichkeiten zur fortgeschrittenen Abstrahierung. Das Ziel der vorliegenden Dissertation war es, zu untersuchen, wie gut verschiedene Arten der Abstraktion das Programmieren mit Concurrent Haskell untersttzen. Concurrent Haskell ist eine Bibliothek fr Haskell, die parallele Programmierung auf Systemen mit gemeinsamem Speicher ermglicht. Im Mittelpunkt der Dissertation standen zwei Forschungsfragen. Erstens wurden verschiedene Synchronisierungsanstze verglichen, die sich in ihrem Abstraktionsgrad unterscheiden. Zweitens wurde untersucht, wie Abstraktionen verwendet werden knnen, um die Komplexitt der Parallelisierung vor dem Entwickler zu verbergen. Bei dem Vergleich der Synchronisierungsanstze wurden Locks, Compare-and-Swap Operationen und Software Transactional Memory bercksichtigt. Die Anstze wurden zunchst bezglich ihrer Eignung fr die Synchronisation einer Priorittenwarteschlange auf Basis von Skiplists untersucht. Anschlieend wurden verschiedene Varianten des Taskpool Entwurfsmusters implementiert (globale Taskpools sowie private Taskpools mit und ohne Taskdiebstahl). Zustzlich wurde fr das Entwurfsmuster eine Abstraktionsschicht entwickelt, welche eine einfache Formulierung von Taskpool-basierten Algorithmen erlaubt. Fr die Untersuchung der Frage, ob Haskells Abstraktionsmethoden die Komplexitt paralleler Programmierung verbergen knnen, wurden zunchst stencil-basierte Algorithmen betrachtet. Es wurde eine Bibliothek entwickelt, die eine deklarative Beschreibung von stencil-basierten Algorithmen sowie ihre parallele Ausfhrung erlaubt. Mit Hilfe dieses deklarativen Interfaces wurde die parallele Implementation vollstndig vor dem Anwender verborgen. Anschlieend wurde eine eingebettete domnenspezifische Sprache (EDSL) fr Knoten-basierte Graphalgorithmen sowie eine entsprechende Ausfhrungsplattform entwickelt. Die Plattform erlaubt die automatische parallele Verarbeitung dieser Algorithmen. Verschiedene Beispiele zeigten, dass die EDSL eine knappe und dennoch verstndliche Formulierung von Graphalgorithmen ermglicht.
Resumo:
In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekrzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhngig voneinander lokale Berechnungen durchfhren und andererseits miteinander kommunizieren drfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszustnden realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Whrend in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschlielich mit einer ausgewhlten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstrke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsanstzen neben Punkt-zu-Punkt-Kommunikationen keine Erhhung der Berechnungsstrke. Desweiteren wird die Ausdrucksstrke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaen die gleiche Ausdrucksstrke wie Einwegmehrkopfautomaten und bilden eine untere Schranke fr die Ausdrucksstrke von PCRA-Systemen mit Einwegkomponenten. Tatschlich sind PCRA-Systeme auch dann strker als PC-Systeme von endlichen Automaten, wenn die Komponenten fr sich genommen die gleiche Ausdrucksstrke besitzen, also die regulren Sprachen charakterisieren. Fr PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexittsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Auerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhhung der Berechnungsstrke bewirken, in Systemen jedoch deren Strke nicht erhhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschlieend werden fr PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalitt, Inklusion, Gleichheit und Endlichkeit bereits fr Systeme mit zwei Restart-Automaten des schwchsten Typs nicht semientscheidbar sind. Fr das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.
Resumo:
Concurrent Smalltalk is the primary language used for programming the J- Machine, a MIMD message-passing computer containing thousands of 36-bit processors connected by a very low latency network. This thesis describes in detail Concurrent Smalltalk and its implementation on the J-Machine, including the Optimist II global optimizing compiler and Cosmos fine-grain parallel operating system. Quantitative and qualitative results are presented.
Resumo:
A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two algorithms, one serial and one parallel, to maintain series-parallel (SP) relationships "on the fly" for fork-join multithreaded programs. The serial SP-order algorithm runs in O(1) amortized time per operation. In contrast, the previously best algorithm requires a time per operation that is proportional to Tarjans functional inverse of Ackermanns function. SP-order employs an order-maintenance data structure that allows us to implement a more efficient "English-Hebrew" labeling scheme than was used in earlier race detectors, which immediately yields an improved determinacy-race detector. In particular, any fork-join program running in T time on a single processor can be checked on the fly for determinacy races in O(T) time. Corresponding improved bounds can also be obtained for more sophisticated data-race detectors, for example, those that use locks. By combining SP-order with Feng and Leisersons serial SP-bags algorithm, we obtain a parallel SP-maintenance algorithm, called SP-hybrid. Suppose that a fork-join program has n threads, T work, and a critical-path length of T[subscript ]. When executed on P processors, we prove that SP-hybrid runs in O((T/P + PT[subscript ]) lg n) expected time. To understand this bound, consider that the original program obtains linear speed-up over a 1-processor execution when P = O(T/T[subscript ]). In contrast, SP-hybrid obtains linear speed-up when P = O(T/T[subscript ]), but the work is increased by a factor of O(lg n).
Resumo:
The underlying assumptions for interpreting the meaning of data often change over time, which further complicates the problem of semantic heterogeneities among autonomous data sources. As an extension to the COntext INterchange (COIN) framework, this paper introduces the notion of temporal context as a formalization of the problem. We represent temporal context as a multi-valued method in F-Logic; however, only one value is valid at any point in time, the determination of which is constrained by temporal relations. This representation is then mapped to an abductive constraint logic programming framework with temporal relations being treated as constraints. A mediation engine that implements the framework automatically detects and reconciles semantic differences at different times. We articulate that this extended COIN framework is suitable for reasoning on the Semantic Web.
Resumo:
The underlying assumptions for interpreting the meaning of data often change over time, which further complicates the problem of semantic heterogeneities among autonomous data sources. As an extension to the COntext INterchange (COIN) framework, this paper introduces the notion of temporal context as a formalization of the problem. We represent temporal context as a multi-valued method in F-Logic; however, only one value is valid at any point in time, the determination of which is constrained by temporal relations. This representation is then mapped to an abductive constraint logic programming framework with temporal relations being treated as constraints. A mediation engine that implements the framework automatically detects and reconciles semantic differences at different times. We articulate that this extended COIN framework is suitable for reasoning on the Semantic Web.
Resumo:
The underlying assumptions for interpreting the meaning of data often change over time, which further complicates the problem of semantic heterogeneities among autonomous data sources. As an extension to the COntext INterchange (COIN) framework, this paper introduces the notion of temporal context as a formalization of the problem. We represent temporal context as a multi-valued method in F-Logic; however, only one value is valid at any point in time, the determination of which is constrained by temporal relations. This representation is then mapped to an abductive constraint logic programming framework with temporal relations being treated as constraints. A mediation engine that implements the framework automatically detects and reconciles semantic differences at different times. We articulate that this extended COIN framework is suitable for reasoning on the Semantic Web.
Resumo:
The underlying assumptions for interpreting the meaning of data often change over time, which further complicates the problem of semantic heterogeneities among autonomous data sources. As an extension to the COntext INterchange (COIN) framework, this paper introduces the notion of temporal context as a formalization of the problem. We represent temporal context as a multi-valued method in F-Logic; however, only one value is valid at any point in time, the determination of which is constrained by temporal relations. This representation is then mapped to an abductive constraint logic programming framework with temporal relations being treated as constraints. A mediation engine that implements the framework automatically detects and reconciles semantic differences at different times. We articulate that this extended COIN framework is suitable for reasoning on the Semantic Web.
Optimal Methodology for Synchronized Scheduling of Parallel Station Assembly with Air Transportation
Resumo:
We present an optimal methodology for synchronized scheduling of production assembly with air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain (CESC). This problem was motivated by a major PC manufacturer in consumer electronics industry, where it is required to schedule the delivery requirements to meet the customer needs in different parts of South East Asia. The overall problem is decomposed into two sub-problems which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as a Linear Programming Problem with earliness tardiness penalties for job orders. For the assembly scheduling problem, it is basically required to sequence the job orders on the assembly stations to minimize their waiting times before they are shipped by flights to their destinations. Hence the second sub-problem is modelled as a scheduling problem with earliness penalties. The earliness penalties are assumed to be independent of the job orders.
Resumo:
This paper proposes a parallel architecture for estimation of the motion of an underwater robot. It is well known that image processing requires a huge amount of computation, mainly at low-level processing where the algorithms are dealing with a great number of data. In a motion estimation algorithm, correspondences between two images have to be solved at the low level. In the underwater imaging, normalised correlation can be a solution in the presence of non-uniform illumination. Due to its regular processing scheme, parallel implementation of the correspondence problem can be an adequate approach to reduce the computation time. Taking into consideration the complexity of the normalised correlation criteria, a new approach using parallel organisation of every processor from the architecture is proposed
