Uma biblioteca para auxiliar o desenvolvimento de aplicações que processam grandes matrizes na memória externa

Abstract

Este trabalho apresenta uma biblioteca, chamada TiledMatrix, para auxiliar o desenvolvimento de aplicações que processam grandes matrizes armazenadas na memória externa. A biblioteca é baseada em algumas estratégias similares ao gerenciamento de uma memória cache e seu objetivo básico é permitir que uma aplicação, desenvolvida para processamento na memória interna, possa ser adaptada para ser processada na memória externa. Ela oferece uma interface para acessar a memória externa similar ao tradicional método de acesso a uma matriz. Além disso, ela divide a matriz em blocos bidimensionais, sendo que os blocos são organizados no disco de modo a tirar proveito do padrão de acesso das aplicações. A fim de reduzir o tempo de transferência do bloco para e do disco, a TiledMatrix utiliza um algoritmo de compressão/descompressão de dados que foi implementado em paralelo para melhorar ainda mais a eficiência da biblioteca. Assim, a TiledMatrix foi implementada e testada em algumas aplicações que requerem intensivo processamento de matrizes tais como: calcular a transposta da matriz, calcular a área de Visibilidade, fluxo acumulado e filrto da mediana. Estas aplicações foram implementadas em duas Versões: uma usando a TiledMatrix e outra usando a Segment, uma biblioteca que está incluída no GRASS, um sistema de informação geográfica open sourca Em média, elas foram 7 Vezes mais rápidas com a TiledMatrix e, em alguns casos, foram em torno de 18 Vezes mais rápidas. A TiledMatrix também foi avaliada com 0 ArcGIS e considerou-se duas aplicações que estão incluídas no ArcGIS: calcular a área de Visibilidade e 0 ñuxo acumulado. Como os testes mostraram, em alguns casos, as aplicações foram mais do que 200 Vezes mais rápidas ao utilizarem a TiledMatrix.

This Work presents a new library, named TiledMatrix, to support the development of applications that process large matrices stored in external memory. The library is based on some strategies similar to cache memory management and its basic purpose is to allow that an application, designed for internal memory processing, can be adapted for external memory. It provides an interface for external memory access that is similar to the traditional method to access a matrix Moreover, it divides the matrix into tWo-dimensional blocks, Where the blocks are organized in the disk to take advantage of access pattern of applications. In order to reduce the transfer time of a block to and from the disk, TiledMatrix uses an algorithm for compression/decompression of data that Was implemented in parallel to further improve the efñciency of the library. The TiledMatrix Was implemented and tested in some applications that require intensive matrix processing such asz computing the transposed matrix and the computation of Viewshed, ñow accumulation and median. These applications Were implemented in two Versionsz one using TiledMatrix and another one using the Segment library that is included in GRASS, an open source GIS. In average, they Were 7 times faster With TiledMatrix and, in some cases, more than 18 times faster. The TiledMatrix performance Was also compared With the ArcGLSÍ For these tests, it Was considered only two applications that are included in ArcGIS: the Uiewshed and the ñow accumulation. As tests have shown, in some cases, the applications Were more than 200 times faster using the TiledMatrix.