Search

Actualmente, las tecnologías de compresión de la información tienen un impacto potencial de rendimiento en el ámbito de las comunicaciones punto a punto y el almacenamiento de datos, y la carga computacional que esto implica está conllevando a necesitar sistemas con prestaciones cada vez más favorables con el paso del tiempo. Hay diversas soluciones implementadas en la codificación por entropía de la información, una de ellas es la codificación aritmética. El Group on Interactive Coding of Images posee una implementación de un codificador aritmético binario adaptativo basado en contexto con palabras de longitud fija, dicho sistema tiene un rendimiento considerablemente alto respecto a otras soluciones. Este trabajo consiste en conseguir una versión más especializada y de mejores prestaciones del codificador anterior mencionado y analizar el rendimiento de ambas versiones en un tipo de procesador determinado. Nowadays, information compression technologies have a potential performance impact in end-to-end communications and data storage, such computational load that this implies is leading to the need for systems with increasingly favourable performance with the pass of time. There are several implemented solutions for entropy coding, such as arithmetic coding. The Group on Interactive Coding of Images has an implementation of a context-adaptive binary arithmetic coder with fixed-length codewords, and this new version of the system achieves a significantly high performance compared to other solutions. This work attempts to achieve a more specialized and better-performing version of the mentioned encoder and to benchmark the performance of both versions on a specific type of processor. Actualment, les tecnologies de compressió de la informació tenen un impacte potencial de rendiment en l'àmbit de les comunicacions punt a punt i l'emmagatzematge de dades, i la càrrega computacional que implica comporta necessitarà sistemes amb prestacions cada vegada més favorables amb el pas el temps. Hi ha diverses solucions implementades en la codificació per entropia de la informació, una d'elles és la codificació aritmètica. El Group on Interactive Coding of Images posseeix una implementació d'un codificador aritmètic binari adaptatiu basat en context amb paraules de longitud fixa, aquest sistema té un rendiment considerablement alt respecte a altres solucions. Aquest treball consisteix a aconseguir una versió més especialitzada i de millors prestacions de l'codificador anterior esmentat i analitzar el rendiment d'ambdues versions en un tipus de processador determinat.

El alineamiento de secuencias se define como la búsqueda de las diferencias que existen entre dos cadenas de caracteres: patrón y texto. Este trabajo utiliza técnicas de Ingeniería de Rendimiento para caracterizar, optimizar y paralelizar el algoritmo Wavefront Aligner de alineamiento de secuencias. Dicho algoritmo mejora el caso medio comparándolo con otros como el Smith-Waterman. Después de hacer una comparativa de la ejecución del algoritmo en procesadores Intel y ARM, se han desarrollado versiones con paralelización en CPU a distintos niveles de granularidad, obteniendo hasta un 7.5x de speedup. Además, se ha desarrollado una versión en GPU que es capaz de calcular la distancia de edición 13 veces más rápido utilizando secuencias de 1000 bases con una tasa de error de hasta el 10%. De la misma forma, aplicando el algoritmo a secuencias con una tasa de error del 60%, se ha logrado obtener un speedup de 69x. L'alineament de seqüències es defineix com la recerca de les diferències entre dues cadenes de caràcters: patró i text. Aquest treball utilitza tècniques d'Enginyeria de Rendiment per a caracteritzar, optimitzar i paral·lelitzar l'algoritme Wavefront Aligner d'alineament de seqüències. Aquest algoritme millora el cas mitjà comparant-lo amb altres com el Smith-Waterman. Després de fer una comparativa de l'execució de l'algoritme en processadors Intel i ARM, s'han desenvolupat versions amb paral·lelització en CPU a diferents nivells de granularitat, obtenint fins a un 7.5x de speedup. A més, s'ha desenvolupat una versió en GPU que és capaç de calcular la distància d'edició 13 vegades més ràpid utilitzant seqüències de 1000 bases amb una taxa d'error de fins al 10%. De la mateixa manera, aplicant l'algoritme a seqüències amb una taxa d'error dl 60%, s'ha aconseguit obtenir un speedup de 69x. Sequence alignment consists in searching for differences between two strings: pattern and text. The present work employs Performance Engineering techniques to characterize, optimize, and parallelize the Wavefront Alignment algorithm. This algorithm improves on the average case compared with others such as the Smith-Waterman. First, we performed a comparison of the execution of the algorithm Intel and ARM processors. Then, we developed a CPU parallel version, exploiting different levels of granularity, obtaining speedups of 7.5x. Finally, we developed a GPU version that is able to calculate the edit distance 13x faster on sequences of 1000 bases allowing up to 10% of error. In the same way, using the algorithm on sequences up to 60% of error we achieve speedups of 69x.

El emparejamiento de secuencias genéticas se puede definir como la búsqueda de las diferencias que existen entre dos cadenas de caracteres: patrón y texto. Existe una gran variedad de algoritmos que resuelven este problema con diferentes costes computacionales. En este trabajo se consideran algoritmos de emparejamiento de tipo exacto y, utilizando técnicas de la Ingeniería de Rendimiento, se mejora la eficiencia de codificación de los mismos. Se obtiene un Speed Up de 3,7x para un algoritmo basado en el peor caso y un Speed Up de 8x en un algoritmo basado en casos medios. Como resultado final se obtiene una versión del programa con un Speed Up de 114x frente a la versión base, para un patrón de 10k caracteres y un texto con el 20% de error respecto al patrón. The matching of genetic sequences can be defined as the search for the differences between two-character strings: pattern and text. A great variety of algorithms can solve this problem with different computational costs. This work studies two exact string matching algorithms and, using Performance Engineering techniques, improves its coding efficiency, attaining a Speed Up of 3,7x for a worst case based algorithm and a Speed Up of 8x on an average case algorithm. As a final result a version with an Speed Up of 114x is achieved compared to the base version, for a 10k character pattern and a text with a 20% difference compared to the pattern. L'aparellament de seqüències genètiques es pot definir com la recerca de les diferències que hi ha entre dues cadenes de caràcters: patró i text. Hi ha una gran varietat d'algoritmes que resolen aquest problema amb diferents costos computacionals. En aquest treball es consideren algoritmes d'aparellament de tipus exacte i, utilitzant tècniques de l'Enginyeria de Rendiment, es millora l'eficiència de codificació dels mateixos. S'obté un Speed Up de 3,7x per a un algoritme basat en el pitjor cas i un Speed Up de 8x en un algoritme basat en casos mitjans. Com a resultat final s'obté una versió del programa amb un Speed Up de 114x enfront de la versió base, per a un patró de 10k caràcters i un text amb el 20% d'error respecte al patró.