FenixEdu™

Dissertação

{en_GB=Cache-Oblivious Nested Loops Based on Hilbert Curves} {} EVALUATED

Detalhes: {pt=Diversos campos da engenharia informática, mais especificamente ciência de dados e inteligência artificial, apresentam dificuldades em processar quantidades imesuráveis de dados. O trabalho desenvolvido por Böhm et al. apresenta-nos uma novidade no campo dos algoritmos, um ciclo aninhado que optimiza a taxa de faltas da cache, sem qualquer conhecimento sobre as suas especificações. Nesta tese será apresentado uma abordagem alternativa e eficiente chamada XOR-Hilbert. O nosso algoritmo apresenta uma taxa de crescimento linear, tanto para o tempo de execução como para memória utilizada. O uso de memória desta abordagem possibilita a reutilização de curvas já computadas, amortizando assim o tempo de execução deste algoritmo para chamadas repetidas da mesma curva., en=Many fields of computer science, especially data science and artificial intelligence, are becoming challenged with an immeasurable amount of data to process. The recent work developed by Böhm et al. presents us a novelty in the field of the algorithms, a Cache-Oblivious Nested For-Loop. This algorithm allows programmers to optimize the cache behaviour of nested for-loops, without any need of knowledge about the CPU cache specifications. In this thesis we will provide an efficient alternative approach to this algorithm, which we called XOR-Hilbert. Our algorithm presents a linear growth-rate of memory and time. The use of memory makes our algorithm stateful, thus allowing the re-utilization of previously computed Hilbert Space-Filling Curves. Which allows the time required to compute another iteration of this curve to be amortized.}
Keywords: {pt=curva de Hilbert, algoritmos cache-oblivious, curvas de preenchimento de espaço, ciclos for baseado na curva de Hilbert, en=cache-oblivious algorithms, Hilbert curve, space-filling curves, cache-oblivious for-loop}

Discussão: novembro 14, 2019, 16:30