Parallelization of SAT on Reconfigurable Hardware

Quoique très difficile à résoudre, le problème de satisfiabilité Booléenne (SAT) est fréquemment utilisé lors de la modélisation d’applications industrielles. À cet effet, les deux dernières décennies ont vu une progression fulgurante des outils conçus pour trouver des solutions à ce problème NP-complet. Deux grandes avenues générales ont été explorées afin de produire ces outils, notamment l’approche logicielle et matérielle. Afin de raffiner et améliorer ces solveurs, de nombreuses techniques et heuristiques ont été proposées par la communauté de recherche. Le but final de ces outils a été de résoudre des problèmes de taille industrielle, ce qui a été plus ou moins accompli par les solveurs de nature logicielle. Initialement, le but de l’utilisation du matériel reconfigurable a été de produire des solveurs pouvant trouver des solutions plus rapidement que leurs homologues logiciels. Cependant, le niveau de sophistication de ces derniers a augmenté de telle manière qu’ils restent le meilleur choix pour résoudre SAT. Toutefois, les solveurs modernes logiciels n’arrivent toujours pas a trouver des solutions de manière efficace à certaines instances SAT. Le but principal de ce mémoire est d’explorer la résolution du problème SAT dans le contexte du matériel reconfigurable en vue de caractériser les ingrédients nécessaires d’un solveur SAT efficace qui puise sa puissance de calcul dans le parallélisme conféré par une plateforme FPGA. Le prototype parallèle implémenté dans ce travail est capable de se mesurer, en termes de vitesse d’exécution à d’autres solveurs (matériels et logiciels), et ce sans utiliser aucune heuristique. Nous montrons donc que notre approche matérielle présente une option prometteuse vers la résolution d’instances industrielles larges qui sont difficilement abordées par une approche logicielle.

Photorealistic Surface Rendering with Microfacet Theory

La synthèse d'images dites photoréalistes nécessite d'évaluer numériquement la manière dont la lumière et la matière interagissent physiquement, ce qui, malgré la puissance de calcul impressionnante dont nous bénéficions aujourd'hui et qui ne cesse d'augmenter, est encore bien loin de devenir une tâche triviale pour nos ordinateurs. Ceci est dû en majeure partie à la manière dont nous représentons les objets: afin de reproduire les interactions subtiles qui mènent à la perception du détail, il est nécessaire de modéliser des quantités phénoménales de géométries. Au moment du rendu, cette complexité conduit inexorablement à de lourdes requêtes d'entrées-sorties, qui, couplées à des évaluations d'opérateurs de filtrage complexes, rendent les temps de calcul nécessaires à produire des images sans défaut totalement déraisonnables. Afin de pallier ces limitations sous les contraintes actuelles, il est nécessaire de dériver une représentation multiéchelle de la matière. Dans cette thèse, nous construisons une telle représentation pour la matière dont l'interface correspond à une surface perturbée, une configuration qui se construit généralement via des cartes d'élévations en infographie. Nous dérivons notre représentation dans le contexte de la théorie des microfacettes (conçue à l'origine pour modéliser la réflectance de surfaces rugueuses), que nous présentons d'abord, puis augmentons en deux temps. Dans un premier temps, nous rendons la théorie applicable à travers plusieurs échelles d'observation en la généralisant aux statistiques de microfacettes décentrées. Dans l'autre, nous dérivons une procédure d'inversion capable de reconstruire les statistiques de microfacettes à partir de réponses de réflexion d'un matériau arbitraire dans les configurations de rétroréflexion. Nous montrons comment cette théorie augmentée peut être exploitée afin de dériver un opérateur général et efficace de rééchantillonnage approximatif de cartes d'élévations qui (a) préserve l'anisotropie du transport de la lumière pour n'importe quelle résolution, (b) peut être appliqué en amont du rendu et stocké dans des MIP maps afin de diminuer drastiquement le nombre de requêtes d'entrées-sorties, et (c) simplifie de manière considérable les opérations de filtrage par pixel, le tout conduisant à des temps de rendu plus courts. Afin de valider et démontrer l'efficacité de notre opérateur, nous synthétisons des images photoréalistes anticrenelées et les comparons à des images de référence. De plus, nous fournissons une implantation C++ complète tout au long de la dissertation afin de faciliter la reproduction des résultats obtenus. Nous concluons avec une discussion portant sur les limitations de notre approche, ainsi que sur les verrous restant à lever afin de dériver une représentation multiéchelle de la matière encore plus générale.

Regelbasiertes Reasoning auf massiv paralleler Hardware

Eine wesentliche Funktionalität bei der Verwendung semantischer Technologien besteht in dem als Reasoning bezeichneten Prozess des Ableitens von impliziten Fakten aus einer explizit gegebenen Wissensbasis. Der Vorgang des Reasonings stellt vor dem Hintergrund der stetig wachsenden Menge an (semantischen) Informationen zunehmend eine Herausforderung in Bezug auf die notwendigen Ressourcen sowie der Ausführungsgeschwindigkeit dar. Um diesen Herausforderungen zu begegnen, adressiert die vorliegende Arbeit das Reasoning durch eine massive Parallelisierung der zugrunde liegenden Algorithmen und der Einführung von Konzepten für eine ressourceneffiziente Ausführung. Diese Ziele werden unter Berücksichtigung der Verwendung eines regelbasierten Systems verfolgt, dass im Gegensatz zur Implementierung einer festen Semantik die Definition der anzuwendenden Ableitungsregeln während der Laufzeit erlaubt und so eine größere Flexibilität bei der Nutzung des Systems bietet. Ausgehend von einer Betrachtung der Grundlagen des Reasonings und den verwandten Arbeiten aus den Bereichen des parallelen sowie des regelbasierten Reasonings werden zunächst die Funktionsweise von Production Systems sowie die dazu bereits existierenden Ansätze für die Optimierung und im Speziellen der Parallelisierung betrachtet. Production Systems beschreiben die grundlegende Funktionalität der regelbasierten Verarbeitung und sind somit auch die Ausgangsbasis für den RETE-Algorithmus, der zur Erreichung der Zielsetzung der vorliegenden Arbeit parallelisiert und für die Ausführung auf Grafikprozessoren (GPUs) vorbereitet wird. Im Gegensatz zu bestehenden Ansätzen unterscheidet sich die Parallelisierung insbesondere durch die gewählte Granularität, die nicht durch die anzuwendenden Regeln, sondern von den Eingabedaten bestimmt wird und sich damit an der Zielarchitektur orientiert. Aufbauend auf dem Konzept der parallelen Ausführung des RETE-Algorithmus werden Methoden der Partitionierung und Verteilung der Arbeitslast eingeführt, die zusammen mit Konzepten der Datenkomprimierung sowie der Verteilung von Daten zwischen Haupt- und Festplattenspeicher ein Reasoning über Datensätze mit mehreren Milliarden Fakten auf einzelnen Rechnern erlauben. Eine Evaluation der eingeführten Konzepte durch eine prototypische Implementierung zeigt für die adressierten leichtgewichtigen Ontologiesprachen einerseits die Möglichkeit des Reasonings über eine Milliarde Fakten auf einem Laptop, was durch die Reduzierung des Speicherbedarfs um rund 90% ermöglicht wird. Andererseits kann der dabei erzielte Durchsatz mit aktuellen State of the Art Reasonern verglichen werden, die eine Vielzahl an Rechnern in einem Cluster verwenden.

Teoría del hardware adaptada a los ciclos formativos de grado superior de informática.

Manual adaptado a los ciclos formativos superiores de informática sobre teoría del hardware, estructurado en seis capítulos cuyos contenidos son: introducción a la informática, representación interna de la información (sistemas, conversión, representación y codificación) la estructura del ordenador, la memoria interna, los microprocesadores y los periféricos.

ADAM: A Decentralized Parallel Computer Architecture Featuring Fast Thread and Data Migration and a Uniform Hardware Abstraction

The furious pace of Moore's Law is driving computer architecture into a realm where the the speed of light is the dominant factor in system latencies. The number of clock cycles to span a chip are increasing, while the number of bits that can be accessed within a clock cycle is decreasing. Hence, it is becoming more difficult to hide latency. One alternative solution is to reduce latency by migrating threads and data, but the overhead of existing implementations has previously made migration an unserviceable solution so far. I present an architecture, implementation, and mechanisms that reduces the overhead of migration to the point where migration is a viable supplement to other latency hiding mechanisms, such as multithreading. The architecture is abstract, and presents programmers with a simple, uniform fine-grained multithreaded parallel programming model with implicit memory management. In other words, the spatial nature and implementation details (such as the number of processors) of a parallel machine are entirely hidden from the programmer. Compiler writers are encouraged to devise programming languages for the machine that guide a programmer to express their ideas in terms of objects, since objects exhibit an inherent physical locality of data and code. The machine implementation can then leverage this locality to automatically distribute data and threads across the physical machine by using a set of high performance migration mechanisms. An implementation of this architecture could migrate a null thread in 66 cycles -- over a factor of 1000 improvement over previous work. Performance also scales well; the time required to move a typical thread is only 4 to 5 times that of a null thread. Data migration performance is similar, and scales linearly with data block size. Since the performance of the migration mechanism is on par with that of an L2 cache, the implementation simulated in my work has no data caches and relies instead on multithreading and the migration mechanism to hide and reduce access latencies.

Image-Based View Synthesis

We present a new method for rendering novel images of flexible 3D objects from a small number of example images in correspondence. The strength of the method is the ability to synthesize images whose viewing position is significantly far away from the viewing cone of the example images ("view extrapolation"), yet without ever modeling the 3D structure of the scene. The method relies on synthesizing a chain of "trilinear tensors" that governs the warping function from the example images to the novel image, together with a multi-dimensional interpolation function that synthesizes the non-rigid motions of the viewed object from the virtual camera position. We show that two closely spaced example images alone are sufficient in practice to synthesize a significant viewing cone, thus demonstrating the ability of representing an object by a relatively small number of model images --- for the purpose of cheap and fast viewers that can run on standard hardware.

Image Based Rendering Using Algebraic Techniques

This paper presents an image-based rendering system using algebraic relations between different views of an object. The system uses pictures of an object taken from known positions. Given three such images it can generate "virtual'' ones as the object would look from any position near the ones that the two input images were taken from. The extrapolation from the example images can be up to about 60 degrees of rotation. The system is based on the trilinear constraints that bind any three view so fan object. As a side result, we propose two new methods for camera calibration. We developed and used one of them. We implemented the system and tested it on real images of objects and faces. We also show experimentally that even when only two images taken from unknown positions are given, the system can be used to render the object from other view points as long as we have a good estimate of the internal parameters of the camera used and we are able to find good correspondence between the example images. In addition, we present the relation between these algebraic constraints and a factorization method for shape and motion estimation. As a result we propose a method for motion estimation in the special case of orthographic projection.

Memory Hierarchy Hardware-Software Co-design in Embedded Systems

The memory hierarchy is the main bottleneck in modern computer systems as the gap between the speed of the processor and the memory continues to grow larger. The situation in embedded systems is even worse. The memory hierarchy consumes a large amount of chip area and energy, which are precious resources in embedded systems. Moreover, embedded systems have multiple design objectives such as performance, energy consumption, and area, etc. Customizing the memory hierarchy for specific applications is a very important way to take full advantage of limited resources to maximize the performance. However, the traditional custom memory hierarchy design methodologies are phase-ordered. They separate the application optimization from the memory hierarchy architecture design, which tend to result in local-optimal solutions. In traditional Hardware-Software co-design methodologies, much of the work has focused on utilizing reconfigurable logic to partition the computation. However, utilizing reconfigurable logic to perform the memory hierarchy design is seldom addressed. In this paper, we propose a new framework for designing memory hierarchy for embedded systems. The framework will take advantage of the flexible reconfigurable logic to customize the memory hierarchy for specific applications. It combines the application optimization and memory hierarchy design together to obtain a global-optimal solution. Using the framework, we performed a case study to design a new software-controlled instruction memory that showed promising potential.

Immersió guiada en el maquinari dels ordinadors. 'Inmersión guiada en el hardware de los ordenadores'.

Resumen tomado de la publicación. Se adjuntan actividades de consolidación de los contenidos del curso. Incluye imágenes

Administración y control de hardware y software para las medianas y grandes empresas en la ciudad de Bogotá

El bajo costo de los elementos utilizados en computación han permitido que cualquier entidad organizacional pueda dotar a la gran mayoría de sus empleados con herramientas de cómputo. Esto ha generado que la Administración y Control de los elementos

Manteniment d'equips informàtics : maquinari i programari. 'Mantenimiento de equipos informáticos : hardware y software'.

Este documento no está publicado

Open Hardware

Presentació sobre la creació de la placa Arduino, i els projectes que s'han fet arreu amb aquesta placa