1,721,018 research outputs found
Planificación simbiótica en arquitecturas CMP
Get PDFMaster en Investigación en Informática, Facultad de Informática, Departamento de Arquitectura de Computadores y Automática , curso 2006-2007Este trabajo presenta un planificador simbiótico a nivel de sistema operativo
para arquitecturas CMP que desarrolla una política de calidad de servicio
basada en la desactivación de cores. El término simbiosis se utiliza actualmente
para referirse a la efectividad con la que se obtiene mayor rendimiento
al ejecutar múltiples hilos simultáneamente en arquitecturas multithreading
(MT) [12]. Sin embargo, este concepto puede extenderse a arquitecturas CMP
(y en consecuencia a arquitecturas CMT) ya que sigue existiendo un notable
índice de compartición de recursos (L2 cache o Front Side Bus) cuyo impacto
sobre el rendimiento de las aplicaciones actuales sigue siendo crítico [13].
El planificador simbiótico ha sido implementado sobre la versión 2.6.21 de
Linux ejecutando sobre una arquitectura CMP de dos vías (Intel Core 2
Duo). En este tipo de arquitecturas, el planificador de Linux 2.6.x garantiza
la calidad de servicio para procesos que ejecutan en un mismo core. Sin
embargo, el sistema permite la ejecución de dos tareas de distinta prioridad
en distintos cores ignorando las posibles degradaciones del rendimiento de
la tarea más prioritaria por motivos de conflicto por el uso de los recursos
compartidos por los cores. Por este motivo, Linux no ofrece calidad de servicio
(QoS) para procesos que ejecuten en distintos cores.Depto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaTRUEunpu
Establecimiento externo de límites de procesos en Linux
Get PDFTrabajo de la asignatura Sistemas Informáticos (Facultad de Informática, Curso 2005-2006)En todo sistema operativo multitarea han de existir límites para regular
el uso equitativo de los recursos.
Un límite consiste en un valor que acota el uso de un determinado
recurso por parte de un proceso dado.
Hasta este momento, las llamadas al sistema existentes en Linux solamente
permitían consultar o modificar los límites de un proceso cualquiera
desde dentro del propio proceso.
El trabajo realizado en el código fuente del kernel aporta las siguientes
mejoras:
permite que los límites se lean o escriban de forma externa a cada
proceso.
define e implementa políticas de modificación (hasta ahora inexistentes).
incluye los límites de procesos dentro del pseudosistema de ficheros
/proc, permitiendo su tratamiento como un fichero de texto
legible.
Así mismo, se ha desarrollado la aplicación gráfica Qlimits utilizando
las librerías Qt que permite el seguimiento y establecimiento de los
límites en un interfaz sencillo.
[ABSTRACT]
In any multitasking operating system, there should exist limits to
regulate fair resources’ use.
A limit consists in a value that bounds resources’ usage by a given
process.
Up to now, the solely support provided by existent system calls in
Linux permits any process to consult or modify its own limits internally.
Work carried out over kernel’s source code provides the following
improvements:
allows limits to be externally read or written outside each process.
defines and implements writing policies (non-existents up to now).
includes processes’ limits in /proc pseudo-filesystem and lets the
limits to be processed as a readable text file.
We’ve also developed the graphic application Qlimits using Qt graphic
libraries to allow process’ tracking and setting in a friendly interface.Depto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaTRUEunpu
Esquema de Paralelización Híbrida para Máquinas de Búsqueda
Get PDFMaster en Investigación en Informática, Facultad de Informática, Departamento de Arquitectura de Computadores y Automática, curso 2007-2008Con la irrupción de las CPU multicores (Chip-level MultiProcessor - CMPs-) se hace imprescindible desarrollar técnicas que aprovechen las ventajas de los CMPs para aumentar el rendimiento de las aplicaciones, haciendo
uso de la computación paralela.
En esta tesis se propone el diseño de una máquina de búsqueda capaz de explotar el nivel de paralelismo disponibles en los los CMPs, para el procesamiento de miles de consultas por unidad de tiempo. En particular, para
esta aplicación y dada la enorme cantidad de recursos computacionales que demanda, es importante desarrollar estrategias paralelas que sean capaces de aprovechar eficientemente el hardware disponible.
El diseño propuesto utiliza técnicas de computación paralela y distribuida para organizar y procesar las consultas. Se propone un esquema de paralelización híbrida basado en los paradigmas de programación BSP y OpenMP que ha sido diseñado para sacar el máximo provecho de las características multi-threading de los CMPs para máquinas de búsqueda. Se describen implementaciones y experimentos realizados sobre dos tipos de procesadores: UltraSPARC T1 de Sun Microsystem y dos nodos Intel Quad-Xeon.Depto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaTRUEunpu
Motores de Búsqueda usando UPC
Get PDFTrabajo de clase de la asignatura Sistemas Informáticos (Facultad de Informática, Curso 2008-2009)En este documento se describen aspectos teóricos y prácticos sobre motores de búsqueda paralelos. El objetivo principal de este trabajo consiste en el diseño e implementación en UPC de un motor de búsqueda para operaciones de tipo OR que sea capaz de obtener
un buen redimiento en escenarios de tráfico elevado.
Para ello el documento comienza con una introducción a los sistemas de recuperación de información. Se incluye un breve paseo por la historia de los métodos de clasificación
y ordenación de colecciones de documentos por el ser humano, así como una descripción más detallada del modelo general de sistemas de búsqueda por computador. Tambien
mencionaremos aspectos sobre recuperación de información de forma distribuida.
La introducción teórica continúa con la presentación de los diversos modelos de programación paralela, centrándonos en el modelo PGAS y en concreto en el lenguaje UPC que ha sido el elegido para la parte práctica del proyecto.
Este documento incluye además información detallada sobre la implementación realizada de un motor de búsqueda centrándose en varios aspectos esenciales: modelos de
datos, algoritmos de ranking, comunicación entre nodos y flujo del programa. El análisis del diseño se acompaña de varias pruebas de rendimiento diseñadas para medir diversos
parámetros de la implementación.
Finalmente se plantean una serie de conclusiones sobre diversos aspectos encontrados durante el desarrollo del proyecto, así como diversos manuales que contienen la información necesaria para poder replicar los entornos de trabajo utilizados.
[ABSTRACT]
This document describes theorical and practical aspects about parallel search engines. The aim of this work consists in the design and implementation in UPC of a search
engine for OR-type operations being able to offer good performance in high traffic scenarios.
To accomplish that the document begins with an introduction to information retrieval sistems. It includes a brief walkthrough about the history of methods used by people
to classify and order collections of document, and a more detailed description about the general model for computer search systems. It also explains some aspects about
distribuited information retrieval.
A presentation of various parallel programming models follows the theorical introduction. We will focus on PGAS model and, specifically, on UPC language which has been
our choice to implement the practical part of this project.
This document also includes detailed information about our search engine implementation, focusing on various essential aspects: data models,ranking algorithms, node communication and program flow. The analysis of the design is followed with some performance tests aimed at measure various parameters of the implementation.
Finally it exposes a series of conclusions about various aspects we met during the development of the project and some manuals which contain the necessary information
needed to be able to replicate the work environments we used.Depto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaTRUEunpu
Planificación de procesos en sistemas multicore asimétricos = Thread Scheduling on Asymmetric Multicore Systems
Get PDFTesis de la Universidad Complutense de Madrid, Facultad de Informática, Departamento de Arquitectura de Computadores y Automática (Arquitectura y Tecnología de Computadores e Ingeniería de Sistemas y Automática), leída el 22-02-2011Symmetric-ISA (Instruction Set Architecture) asymmetric-performance multicore processors (AMPs) were shown to deliver higher performance per watt and area than its symmetric counterparts [1, 2], and so it is likely that future multicore processors will combine a few fast cores characterized by complex pipelines, high clock frequency, high area requirements and power consumption, and many slow
ones, characterized by simple pipelines, low clock frequency, low area requirements and power consumption.
Recent research has highlighted that eficiency of AMP systems could be improved using two kinds of core specializations [3, 4]. The former ensures that fast cores
are used for those applications that eficiently utilize these cores' "expensive" features, while slow cores would be used for applications spending a majority of their
execution time stalling the processor, thus utilizing complex cores ineficiently. The latter leverages the efectiveness of these systems by using fast cores to accelerate sequential phases of parallel applications, and devoting slow cores to running parallel phases.
To fully tap into the potential of specialization, the operating system (OS) must be aware of the hardware asymmetry when making scheduling decisions and map
applications to cores in consideration of their performance characteristics. While the design and the theoretical benefits of AMPs have been extensively investigated [1, 5],
the study of real-world operating system support for these upcoming architectures has not been addressed comprehensively to date. So the questions as to whether
this potential can be delivered eficiently by the operating system to unmodified applications, and what the associated overheads are remain open.
In this thesis, we propose a set of OS-level scheduling algorithms aimed to unleash the potential of specialization. These algorithms have been implemented on
an actual operating system and extensively evaluated on real multicore hardware made asymmetric via dynamic voltage and frequency scaling (DVFS). Notably, none of these algorithms require changes to applications but only moderate changes to the target operating system, providing proof of concept towards lightweight OS support for asymmetric hardware. Our evaluation also includes an extensive comparison with previously proposed asymmetry-aware schedulers to provide a clearer understanding of the pros and cons behind our proposals. [RESUMEN]Los procesadores multicore asimétricos con repertorio común de instrucciones – AMPs (Asymmetric Multicore Processors)– han sido propuestos recientemente como firme alternativa a los multicores simétricos actuales, prometiendo un mayor rendimiento por vatio. Por ello, es probable que próximas generaciones de procesadores multicore integren, en un mismo chip, unos pocos cores complejos junto con numerosos cores más simples y de bajo consumo. El potencial de los sistemas AMP puede extraerse principalmente mediante dos técnicas especialización de cores. La primera técnica asegura el uso de cores complejos por parte de las aplicaciones que explotan más eficientemente las sofisticadas características microarquitectónicas de éstos, y relega a cores simples el resto de aplicaciones. La segunda técnica explota la capacidad de aceleración monohilo de los cores complejos para la ejecución de fases secuenciales en las aplicaciones, mientras que las fases paralelas se ejecutan en cores simples. Aunque los beneficios de la especialización de cores se han hecho patentes en diversos estudios, no se ha llevado a cabo hasta la fecha un análisis exhaustivo del soporte necesario en un sistema operativo real que permita trasladar estos beneficios de manera transparente a las aplicaciones. En esta tesis hemos mostrado cómo y hasta qué punto, las estrategias de especialización pueden explotarse mediante planificación de procesos en el sistema operativo. Para ello, hemos propuesto diversos algoritmos de planificación para AMPs implementados en un sistema operativo real y evaluados exhaustivamente en plataformas multicore asimétricas emuladas. Las principales contribuciones de esta tesis son las técnicas propuestas para la detección y aceleración de fases secuenciales en software paralelo, así como los modelos de estimación del speedup que experimentan las aplicaciones al ejecutar en cores complejos con respecto a cores simples.Depto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaTRUEpu
Calidad de servicio en procesadores con multithreading simultaneo (SMT)
Get PDFTrabajo de la asignatura Sistemas Informáticos (Facultad de Informática, Curso 2005-2006)SMT: Implementación de un algoritmo para dar Calidad de Servicio Aunque en general, con hyperthreading (mecanismo cuya base es tener varios procesadores lógicos sin tener todo el hardware duplicado) se consigue mayor productividad,
dicha mejora puede conseguirse a expensas de disminuir los recursos disponibles para procesos críticos.
Experimentos previos indican que para conseguir políticas que maximicen el número de plazos cumplidos por tareas con requisitos de tiempo real suave, no basta con la asignación de prioridades tradicional de Linux, sino que es necesario tener en cuenta SMT.
Resulta interesante, por tanto, estudiar el efecto de una planificación basada en calidad de servicio que optimice el rendimiento de una tarea sin degradar la respuesta del resto de procesos ejecutándose en el sistema.
Nuestra propuesta de calidad de servicio se ha llevado a cabo para procesadores de la familia Pentium 4 e Intel Xeon y sobre el kernel de Linux para la familia 2.6; cuyos
mecanismos para calidad de servicio para este tipo de procesadores consideramos no están suficiéntemente estudiados.
[ABSTRACT]
SMT: Implementing an algorithm for Quality of Service
Although normally, with hyperthreading (mecanism based in having various logical processors without having all the software duplicated), bigger throughput is obtained; this
improvement can force a reduction in the available resources for critical processes.
Previous experiments has shown that obtaining policies which maximize the number of carried out term’s by task with real time requirements, is not enough the traditional
linux priority asignation, it’s necesary taking account of SMT.
So it’s interesting estudying the effect of Quality of Service based policy that optimizes one task’s throughput without affecting other processes’ response time in the system.
Our Quality of Service proposal has been developed for Pentium 4 e Intel Xeon family processors and over the kernel 2.6 series. To the best of our knowledge, scheduling
mechanisms to obtain Quality of Service for this kind of processors hasn’t been yet implemented on real systems.Depto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaTRUEunpu
Simulador de sistema de memoria de caches adaptativas con PIN
Get PDFTrabajo de la asignatura Sistemas Informáticos (Facultad de Informática, Curso 2005-2006)El objetivo de nuestro proyecto es implementar un simulador dinámico de caches adaptativas. Con él podemos comprobar la eficacia de las técnicas de hardware adaptativo sobre diversos benchmarks. En primer lugar, se ha implementado un sistema de caches de datos e instrucciones con varios niveles, permitiendo configurar completamente las características de cada nivel. Tras esto, añadimos la posibilidad de adaptar dinámicamente el número de vías
en función de la tasa de fallos. Para instrumentar dinámicamente el código hemos utilizado la herramienta Pin desarrollada por Intel. Como era necesario validar los resultados obtenidos, los hemos comparado con los obtenidos por otro simulador de caches, Dinero IV. Las pruebas demuestran que el error entre unos y otros es muy reducido. Por último se llevaron a cabo pruebas para estudiar la eficacia de los mecanismos adaptativos en cache. Los resultados obtenidos demuestran que, sin incrementar significativamente la tasa de fallos, sí se consigue reducir el número de vías de cada nivel. Esto supone
una mejora en el consumo energético de la jerarquía de memoria.
[ABSTRACT]
The goal of our project is to develop an adaptative cache dynamic simulator. We can use it to test the e®ectiveness of adaptative hardware techniques in several benchmarks. First, we have built a shared multilevel cache.
It is possible to configure completely each level modifying its configuration file. After that, we add the possibility of dynamically adapt the number of ways according to miss rate. To dynamically instrument code we have used Pin, property of Intel. In the way to validate results, we have compared our memory system with Dinero IV, another cache simulator. The comparative demonstrate results are very close. Finally, tests were carried out to study the
effectiveness of adaptative methods applied in caches. Results demonstrate that, without increasing miss rate significantly, it is possible to reduce the average number of ways each level has. This involves an improvement in the
power consumption of the memory hierarchy.Depto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaTRUEunpu
Desarrollo de solvers CFD híbridos en plataformas heterogéneas
Get PDFTesis inédita de la Universidad Complutense de Madrid, Facultad de Informática, Departamento de Arquitectura de Computadoras y Automática, leída el 19-10-2015La comunidad de dinámica de fluidos computacional (CFD) siempre ha explorado nuevas formas para aprovechar las plataformas de computación de alto rendimiento en su continua búsqueda de simulaciones más rápidas y precisas. Durante los últimos años, la irrupción de las arquitecturas heterogéneas ha sido una de las tendencias más importantes en este campo y se han creado nuevos desafíos y oportunidades para optimizar el rendimiento de los solvers considerados estado del arte. En este trabajo hemos explorado algunas de estas nuevas oportunidades. Nuestros solvers objetivo se enmarcan en el dominio de los flujos incompresibles. A pesar de los significativos avances que han logrado las metodologías más avanzadas en este campo, un aspecto que sigue necesitando de más investigación es la aceleración de los solvers incompresibles, en particular cuando se manejan problemas de gran dimensión con geometrías complejas. El coste computacional de este tipo de solvers está dominado frecuentemente por la solución de la Ecuación de Poisson para la determinación de la presión. Nuestra primera contribución en esta tesis ha explorado la aceleración en sistemas heterogéneos de los denominados métodos rápidos para la solución de esta ecuación. Primero investigamos el rendimiento de diferentes algoritmos en procesadores multicore y en GPUs por separado y posteriormente estudiamos la ejecución conjunta en ambos tipos de procesadores. Como era previsible, en los procesadores multicore las aproximaciones de grano grueso proporcionan los mejores resultados, mientras que en GPUs es mejor utilizar alternativas de grano fino basadas en estrategias de reducción cíclica extendidas. Nuestra principal contribución de esta parte de la tesis ha sido el diseño de una aproximación heterogénea que es capaz de combinar ambas estrategias y beneficiarse del solapamiento entre CPUs y GPUs. Desafortunadamente, el rendimiento global que estos solvers rápidos no satisface los objetivos que nos habíamos establecido. Es por ello que en la segunda parte de esta tesis hemos tratado de superar esa limitación intrínseca de los solvers basados en Navier Stokes estudiando como alternativa el método de Lattice-Boltzmann (LBM). El diseño de implementaciones paralelas de LBM se ha estudiado de forma extensiva y han mostrado que puede alcanzar grandes rendimientos en aceleradores del tipo GPU. Sin embargo, las simulaciones que pretendemos realizar presentan geometrías complejas y no basta con solvers LBM puros. Una aproximación prometedora para tratar estos problemas es la combinación de LBM con el método de las fronteras immersas (IB: Immersed Boundaries). En primer lugar hemos comprobado como implementaciones directas de ambos métodos (LBM e IB) por separado no escalan bien, ya que la corrección IB degrada de forma notable el rendimiento global. Nuestra principal contribución ha sido el diseño de una implementación híbrida que permite solapar la ejecución de ambos métodos (LBM e IB) en plataformas heterogéneas, ocultando de forma efectiva las penalizaciones introducidas por IB. De hecho, el solvers híbrido es capaz de ocultar totalmente la penalización causada por la corrección IB. La principal idea de este trabajo ha consistido en la restructuración de los códigos para permitir una mejor coordinación entre el procesador host y el acelerador, permitiendo el solapamiento de sus ejecuciones. Con dicho solapamiento hemos sido capaces de ocular el coste de las transferencias de datos entre el host y el acelerador y las penalización causada por cuellos de botella secuenciales, es decir, hemos usado el procesado host como una acelerador de fases secuenciales del códigoDepto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaTRUEunpu
List ranking on multicore systems
No full textMáster en Investigación en Informática, Facultad de Informática, Departamento de Arquitectura de Computadores y Automática, curso 2009-2010En este proyecto hemos revisado la implementación de algoritmos paralelos para el ranking de listas enlazadas en procesadores multicore. Este tipo de algoritmos exhibe patrones de acceso a memoria fuertemente irregulares que no se benefician de los mecanismos agresivos que integran las arquitecturas actuales para ocultar los costosos accesos a memoria (caches, mecanismos de prebúsqueda, ...). Debido a
esta característica intrínseca, el rendimiento de cualquier algoritmo para el ranking de listas esta limitado por los accesos a memoria no consecutivos. En los algoritmos
paralelos los problemas de rendimiento se agravan ya que los patrones de acceso irregular suelen provocar mayor contención por recursos compartidos y por lo tanto,
continua siendo un importante desafío disear algoritmos eficientes para esta aplicación.
Desde comienzos de los 80 se han propuesto un buen número de alternativas para obtener algoritmos paralelos eficientes, pero recientemente ha aumentado el interés debido al auge de muchas aplicaciones, muchas de ellas relacionados con Internet, donde se manejan grandes cantidades de datos almacenadas en estructuras de datos tipo listas enlazadas. Algunos artículos recientes han analizado la implementación de estos algoritmos en GPUs, pero los sistemas basados en procesadores multicore todavía dominan ampliamente el mercado de servidores para muchas de
estas aplicaciones. Nos hemos centrado en el algoritmo de Helman y Jájá’s, ya que los intentos por obtener resultados satisfactorios con otros algoritmos, como ha sido el caso de la conocida técnica de pointer jumping propuesta por Wyllie no ha dado resultados atisfactorios. Como principal aportación mostramos como es posible optimizar el algoritmo standard de Helman y Jájá’s para reducir el número de accesos a memoria no consecutivos. También sugerimos una implementación dinámica basada en el paradigma de work-stealing paradigm, aunque todavía, los resultados preliminares no son satisfactorios.
[ABSTRACT]
In this project we have revisited the implementation of parallel linked-list ranking algorithms on modern Multicore processors. This computation exhibits highly irregular memory referencing patterns, which do not typically benefit from the aggressive mechanisms that integrate current architectures to hide the large latency of main-memory accesses (cache hierarchies, data pre-fetching, ...). Because of this intrinsic characteristic, the performance of any List Ranking algorithm on modern cache-based processors is seriously limited by non-contiguous memory accesses. On a parallel setting, performance is further aggravated since concurrent irregular memory access patterns usually cause more contention for shared memory resources and as such, List Ranking represents a challenging problem for parallel computing.
The development of parallel algorithms for List Ranking has received significant attention in previous literature dating back to the early 80’s but most recently, the emerge of many Internet applications that involve extremely large amount of data with linked structures has renewed the interest in List Ranking. Some recent papers have discussed the implementation of these algorithms on modern GPUs but
multicore systems still dominate the server market for many applications.
We have focused on the Helman and Jájá’s algorithm, since any attempt to achieve satisfactory results with other algorithms such as the famous Wyllie’s pointer jumping technique have proven to be ineffective. As main contribution we have shown how the standard Helman and J´aj´a’s implementation can be optimized to reduce the number of non-contiguous memory access. We have also suggested a dynamic parallel version based on the work-stealing paradigm, although preliminary results are still unsatisfactory.Depto. de Arquitectura de Computadores y AutomáticaFac. de InformáticaFALSEunpu
- …
