No description available.

[EN] In this research, a new model of computing is presented, within the framework of natural computing and computer models inspired by biology: Networks of Genetic Processors (NGP). This new model is based on the one hand, by the family of networks of bio-inspired processors, specifically Networks of Evolutionary Processors (NEP) and Networks of Splicing Processors (NSP), and on the other hand by Genetic Algorithms. We can define the new model as a network of biologically-inspired processors where operations used by processors are crossover and mutation. One of the major interests studying the NGP is the computational power of the operations of crossover and mutation acting together. The NEP is a complete model that uses operations of symbol mutation: insertion, substitution and deletion, the NSP is a complete model that uses splicing operations, but the NEP is no longer a complete model using only substitution operations, as it happens to the NSP if we restrict the context of its splicing rules to the empty context. The study of the new model presented here responds to what happens when we put together in a single model the substitution rules from the NEP (called mutation rules) and the splicing rules with empty context from the NSP (called crossover rules). When we work with networks of biologically-inspired processors there are two basic types of networks, accepting networks and generating networks. These types of networks are mainly used to work at a theoretical level or to solve decision problems. To work on a more practical level such as solving optimization problems, we propose a new type of network, Networks of Genetic processors as Parallel Genetic Algorithms, inspired by the Parallel Genetic Algorithms. In this work we prove the computational completeness of our new model by showing that it is equivalent to the Turing machine. We prove the computational completeness of Parallel Genetic Algorithms by using this result and the similarity between the NGP and Parallel Genetic Algorithms. Moreover, we propose a characterization of the Chomsky hierarchy by using the NGP. Here, we simulate every grammar in the language classes of the Chomsky's hierarchy by using a NGP with an small number of processors required for each simulation. Hence, it gives an appreciable idea of the descriptional complexity of the different families of languages. Finally, in this work there is an experimental study of the behavior of the model for the resolution of some practical problems. First, we design and implement a simulator that allows the execution of networks of Genetic Processors in any of its three defined types: accepting networks, generating networks or as Parallel Genetic Algorithms. This allows us to test the model with different optimization problems. Then, we make a study to see if the new model could solve NP problems in polynomial time. We use the decision problem of Hamiltonian cycle in a graph. Finally, we test the simulator with two optimization problems showing a good computational behavior. The problems are the Multidimensional Knapsack problem and the Traveling Salesman problem. / [ES] Desde la rama de la biocomputación, la computación con modelos inspirados en la biología, esta investigación presenta un nuevo modelo de computación: las Redes de Procesadores Genéticos (NGP). Este nuevo modelo parte, por un lado, de la familia de modelos de redes de procesadores, más concretamente de las Redes de Procesadores Evolutivos (NEP) y las Redes de Procesadores de Splicing (NSP), y por otra parte se inspira en los Algoritmos Genéticos. Así pues, se puede definir de manera informal el nuevo modelo como una red de procesadores bioinspirados donde las operaciones utilizadas por los procesadores son operaciones de cruce y mutación. Uno de los mayores intereses del estudio de las NGP es la capacidad conjunta de las operaciones de cruce y mutación, las NEP son un modelo completo que utiliza operaciones de evolución, es decir, inserción, substitución y borrado, las NSP son un modelo completo que utiliza operaciones de splicing, pero las NEP dejan de ser un modelo completo al usar sólo operaciones de substitución, al igual que le pasa a las NSP si restringimos el contexto de sus reglas de splicing a vacío. El estudio del nuevo modelo aquí presentado da respuesta a qué es lo que pasa cuando juntamos en un sólo modelo las operaciones de sustitución de las NEP (llamadas reglas de mutación) y las operaciones de splicing con contexto vacío de las NSP (llamadas reglas de cruce). Cuando se trabaja con redes de procesadores bioinspirados se definen principalmente dos tipos de redes, las redes aceptoras y las redes generadoras. Estos tipos de redes sirven principalmente para trabajar a un nivel teórico o para resolver problemas de decisión. Para trabajar a un nivel más práctico como por ejemplo con problemas de optimización, se propone un nuevo tipo de red, las Redes de Procesadores Genéticos como Algoritmos Genéticos Paralelos, llamadas así por inspirarse en los Algoritmos Genéticos Paralelos. A nivel teórico, se ha podido demostrar la completitud computacional del modelo, con lo que su potencia de computación se sitúa al mismo nivel que el de las maquinas de Turing. A raíz de este resultado y dada la gran similitud entre las NGP y los Algoritmos Genéticos Paralelos, en este trabajo se demuestra que éstos también son un modelo de computación completo. Por otra parte se ha podido realizar una caracterización de la jerarquía de Chomsky utilizando las NGP, para ello se simula cada una de las gramáticas que definen las cuatro familias de lenguajes de dicha jerarquía observando el mínimo número de procesadores necesarios para cada simulación, lo cual da una idea apreciable de la diferencia de complejidad entre las diferentes familias. No falta en este trabajo un estudio de la parte más práctica del modelo con la realización de algunas tareas. Primero se ha diseñado e implementado un simulador que permite la ejecución de Redes de Procesadores Genéticos en cualquiera de sus tres vertientes aquí definidas, como aceptoras, como generadoras o como Algoritmos Genéticos Paralelos, esto permite realizar pruebas con diferentes problemas de optimización. A continuación se ha realizado un estudio para ver si el nuevo modelo era capaz de resolver problemas NP en tiempo polinómico, para ello se ha trabajado con el problema de ver si existe algún ciclo Hamiltoniano en un grafo. Finalmente se ha probado el simulador con dos problemas de optimización en los que se ha detectado un buen comportamiento del mismo, los problemas utilizados han sido el problema de la mochila multidimensional y el problema del viajante de comercio. / [CAT] Des de la branca de la biocomputació (la computació amb models inspirats amb la biologia) aquesta investigació presenta un nou model de computació: Les Xarxes de Processadors Genètics (NGP). Aquest nou model ve, d'una banda, de la família de models de xarxes de processadors, més concretament de les Xarxes de Processadors Evolutius (NEP) i de les Xarxes de Processadors de Splicing (NSP) i d'altra banda s'inspira als Algoritmes Genètics. Així doncs, es pot definir d'una manera informal el nou model com una xarxa de processadors bioinspirats on les operacions utilitzades per els processadors són operacions de creuament i mutació. Un dels elements més interessants de l'estudi de les NGP és la capacitat conjunta de les operacions de creuament i mutació, les NEP són un model complet que utilitza operacions evolutives, és a dir, insercions, substitucions i esborrats, les NSP són un model complet que utilitza operacions de splicing, però les NEP deixen de ser un model complet al gastar sols operacions de substitució, al igual que li passa a les NSP si restringim el context de les seues regles de splicing a buit. L'estudi del nou model presentat ací dóna resposta a què és el que passa quan ajuntem a un sol model les operacions de substitució de les NEP (anomenades regles de mutació) i les operacions de splicing amb context buit de les NSP (anomenades regles de creuament). Quan es treballa amb xarxes de processadors bioinspirats es defineixen principalment dos tipus de xarxes, les xarxes aceptores i les xarxes generadores. Aquests tipus de xarxes s'utilitzen principalment per a treballar a nivell teòric o per a resoldre problemes de decisió. Per treballar a un nivell més pràctic, com per exemple amb problemes d'optimització, es proposa un nou tipus de xarxa, les Xarxes de Processadors Genètics com Algoritmes Genètics Paral·lels, anomenats així per estar inspirats en els Algoritmes Genètics Paral·lels. A nivell teòric, s'ha pogut demostrar la completitut computacional del model, amb el que la seua potència computacional es situa al mateix nivell que les màquines de Turing. Degut a aquest resultat i donada la gran similitud entre les NGP i els Algoritmes genètics Paral·lels, en aquest treball es demostra que aquestos també són un model computacional complet. D'altra banda, s'ha pogut realitzar una caracterització de la jerarquia de Chomsky utilitzant les NGP, aquest procés es realitza simulant cada una de les gramàtiques que defineixen les quatre famílies de llenguatges d'aquesta jerarquia observant el mínim nombre de processadors necessaris per a cada simulació, el que ens dóna una idea apreciable de la diferència de complexitat entre les diferents famílies. No falta a aquest treball un estudi de la part més pràctica del model com la realització d'algunes tasques. Primer s'ha dissenyat i implementat un simulador que permet l'execució de Xarxes de Processadors Genètics a qualsevol de les seues tres varietats ací definides, com aceptores, com a generadores o com a Algoritmes Genètics Paral·lels, amb el que podem realitzar proves amb diferents problemes d'optimització. A continuació s'ha realitzat un estudi per vore si el nou model era capaç de resoldre problemes NP en un temps polinòmic, estudi que hem realitzat utilitzant el problema de saber si existeix algun cicle Hamiltonià en un graf. Finalment s'ha provat el simulador amb dos problemes d'optimització als que s'ha comprovat que té un bon comportament, els problemes utilitzats són el problema de la motxilla multidimensional i el problema del viatjant de comerç. / Campos Frances, M. (2016). REDES DE PROCESADORES GENÉTICOS [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/61452 / TESIS

No description available.

Esta tesis se enmarca en el ámbito de las técnicas de mejora de la eficiencia de ejecución (disminución del consumo y aumento de la velocidad) en el diseño de procesadores orientados a la ejecución de aplicaciones multimedia. En los últimos años la proliferación de los sistemas de baja potencia (móviles, PDAs, etc.) ha generado una enorme demanda de capacidad de cálculo en estos dispositivos. Estos sistemas han de enfrentarse al difícil reto de mejorar sus prestaciones manteniendo limitado su consumo.Se puede ver claramente que la evolución seguida por las arquitecturas de bajo consumo se aparta de la tendencia marcada años atrás por los procesadores de alto rendimiento. En el segmento de alta velocidad los aumentos significativos del rendimiento se han obtenido habitualmente a cambio de ejecutar más instrucciones por unidad de tiempo, muchas de ellas de forma especulativa.En esta tesis se propone un novedoso sistema de cálculo para contenidos multimedia: el cálculo difuso. Este sistema permite aprovechar, por un lado, la redundancia de los contenidos multimedia y, por otro, la tolerancia respecto a los errores exhibida por los destinatarios de los contenidos (los sentidos humanos) para obtener grandes ahorros de tiempo y energía en el procesado.Para conseguir estos objetivos, el cálculo difuso se basa en un principio muy simple: para obtener un resultado correcto para una operación no es necesario realizar un cálculo exacto. O dicho de otro modo, no importa cometer errores si no hay nadie que pueda distinguirlos. Este principio, que aplicado a otros ámbitos (bases de datos, por ejemplo) puede parecer una aberración, cobra pleno sentido cuando se aplica a los contenidos multimedia. De hecho, hace muchos años que este principio se está empleando asiduamente, solo que a otro nivel: Los algoritmos de compresión más usuales (mp3 y jpeg por ejemplo) se basan en obtener resultados inexactos para lograr reducir la cantidad de información que es necesario almacenar o transmitir. En esta tesis proponemos hacer exactamente lo mismo pero para conseguir aumentar la velocidad de los procesadores y reducir la energí¬a que consumen.La implementación de un sistema de cálculo difuso se ha abordado desde dos perspectivas distintas: el cálculo difuso de instrucciones y el cálculo difuso de regiones. El cálculo difuso de instrucciones, como su mismo nombre indica, consiste en la substitución de una instrucción determinista (como una multiplicación) por otra instrucción que de lugar a un resultado aproximado. Esto se ha realizado, o bien mediante unidades funcionales que operan sobre un número menor de bits, o bien mediante un sistema de memorización tolerante.El cálculo difuso de regiones, por su parte, consiste en la substitución de un fragmento de código completo por un mecanismo hardware-software que es capaz de generar un resultado aproximado para las mismas entradas que el código original.Los resultados obtenidos muestran que las ideas propuestas en esta tesis dan lugar a importantes ahorros de energí¬a y tiempo en el procesado de contenidos multimedia sin modificar sustancialmente (es decir, de forma apreciable) la salida de dicho procesado. Se han obtenido ahorros del 15% en tiempo y del 25% en energía para un conjunto de programas multimedia con calidades de salida muy buenas.En resumen, a lo largo de la tesis se han realizado las siguientes aportaciones:- Se ha propuesto una nueva forma de procesar datos: el cálculo difuso}, que permite ahorrar tiempo y energía en el procesado de archivos multimedia.- Se han propuesto diferentes implementaciones de cálculo difuso: la memorización tolerante de regiones, la memorización tolerante de instrucciones y el uso de unidades funcionales reducidas. Todos ellos, sistemas que pueden integrarse en un procesador actual.

Se ha determinado, en una arquitectura multi-Core SMP, el lugar donde incorporar el PP o el HPP sin alterar el ISA del resto de los core. Se ha obtenido una familia de procesadores que ejecutan los algoritmos de Petri para dar solución a sistemas reactivos y concurrentes, con una sólida verificación formal que permite la programación directa de los procesadores. Para esto, se ha construido el hardware de un PP y un HPP, con un IP-Core en una FPGA, integrado a un sistema multi-Core SMP, que ejecuta distintos tipo de RdP. Esta familia de procesadores es configurable en distintos aspectos: - Tamaño del procesador (cantidad de plazas y transiciones). - Procesadores con tiempo y procesadores temporales. - Arquitectura heterogénea, que permite distribuir los recursos empleados para instanciar el procesador según se requiera, y obtener un ahorro sustancial. - La posibilidad de configurar el procesador en pos de obtener los requerimientos y minimizar los recursos. Muy valorado en la construcción de sistemas embebidos. En los sistemas con alta necesidad de concurrencia y sincronización, donde se ha evaluado este procesador, las prestaciones han mostrado una importante mejora en el desempeño. El procesador tiene la capacidad de resolver simultáneamente, por conjuntos múltiples disparos, lo que disminuye los tiempos de consulta y decisión, además los programas ejecutados cumplen con los formalismos de las RdP extendidas y sincronizadas, y los resultados de su ejecución son determinísticos. Los tiempos de respuesta para determinar una sincronización son de dos ciclos por consulta (entre la solicitud de un disparo y la respuesta).

En la presente Tesis se proponen soluciones para aliviar el alto coste, en rendimiento y consumo, de las comunicaciones intra-chip a través de los alambres globales. En concreto, se propone utilizar redes heterogéneas que permiten una mejor adaptación a las necesidades de los diferentes tipos de mensajes de coherencia.Nuestra primera propuesta consiste en dividir las respuestas con datos en un mensaje corto crítico, enviado usando enlaces de baja latencia, y un mensaje largo no crítico enviado usando enlaces de bajo consumo. La segunda propuesta utiliza la compresión de direcciones en el contexto de una red de interconexión heterogénea que permite la compresión de mayoría de los mensajes críticos en unos pocos bytes, siendo transmitidos usando enlaces de muy baja latencia. Finalmente, se explora el uso de la prebúsqueda por hardware para aliviar los problemas derivados de las altas latencias de los enlaces globales. / In this thesis we propose different ways to alleviate the high cost, in terms of performance and power consumption, of the intra-chipcommunications using global wires. In particular, we considerheterogeneous networks to obtain a better match between thenetwork-on-chip and the needs of the different types of coherencemessages.Our first contribution proposes the partitioning of reply messages with data into a short critical message, which is sent using low-latency links, as well as a long non-critical message sent using low-power links. The second contribution exploits the use of address compression in the context of a heterogeneous interconnect to allow most of the critical messages to be compressed in a few bytes and transmitted using very low latency links. Finally, we explore the use of heterogeneous networks in the context of hardware prefetching to alleviate the problems caused by high latencies of global links.

No description available.

En la última década los ingenieros informáticos se han enfrentado a profundos cambios en el modo en que se diseñan y fabrican los microprocesadores. Los nuevos procesadores no solo deben ser más rápidos que los anteriores, también deben ser factibles en términos de energía y disipación térmica, sobre todo en dispositivos que trabajan con baterías. Los problemas relacionados con consumo y temperatura son muy comunes en estos procesadores. En esta Tesis analizamos el rendimiento, consumo energético y precisión de diferentes mecanismos de reducción de consumo y descubrimos que no son suficientemente buenos para adaptarse a un límite de consumo con una penalización de rendimiento razonable. Para solucionar este problema proponemos diversas técnicas a nivel de microarquitectura que combinan de manera dinámica varios mecanismos de reducción de consumo para obtener una aproximación al límite de consumo mucho más precisa con una penalización de rendimiento mínima. / In the last decade computer engineers have faced changes in the way microprocessors are designed. New microprocessors do not only need to be faster than the previous generation, but also be feasible in terms of energy consumption and thermal dissipation, especially in battery operated devices. In this Thesis we worked in the design, implementation and testing of microarchitecture techniques for accurately adapting the processor performance to power constraints in the single core scenario, multi-core scenario and 3D die-stacked core scenario. We first designed “Power-Tokens”,to approximate the power being consumed by the processor in real time. Later we proposed different mechanisms based on pipeline throttling, confidence estimation, instruction criticality information, to adapt the processor to a predefined power budget . We also propose some layout optimizations for 3D die-stacked vertical designs.

Cache coherence protocols based on tokens can provide low latency without relying on non-scalable interconnects thanks to the use of efficient requests that are unordered. However, when these unordered requests contend for the same memory block, they may cause protocols races. To resolve the races and ensure the completion of all the cache misses, token protocols use a starvation prevention mechanism that is inefficient and non-scalable in terms of required storage structures and generated traffic. Besides, token protocols use non-silent invalidations which increase the latency of write misses proportionally to the system size. All these problems make token protocols non-scalable. To overcome the main problems of token protocols and increase their scalability, we propose a new starvation prevention mechanism named Priority Requests. This mechanism resolves contention by an efficient, elegant, and flexible method based on ordered requests. Furthermore, thanks to Priority Requests, efficient techniques can be applied to limit the storage requirements of the starvation prevention mechanism, to reduce the total traffic generated for managing protocol races, and to reduce the latency of write misses. Thus, the main problems of token protocols can be solved, which, in turn, contributes to wide their efficiency and scalability. / Cuesta Sáez, BA. (2009). Efficient techniques to provide scalability for token-based cache coherence protocols [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/6024 / Palancia