a) Blomman bilden är 3820 × 3820 bild (14,5 miljoner pixlar) och innehåller 3,7 miljoner icke-vita pixlar. Koordinaterna för dessa pixlar visas som färger i (b). Vi lagrar bilden i en hash tabell under en 0.99 belastningsfaktor: hash tabellen innehåller bara 3,73 miljoner poster. Dessa används som nycklar för hashing. c) Tabellen som erhålls med en typisk randomiserande hashfunktion: Nycklarna sprids slumpmässigt och all samstämmighet går förlorad. (d) Vår rumsligt sammanhängande hashtabell, byggd parallellt på GPU. Bordet är byggt i 15 ms på en GeForce GTX 480, och bilden rekonstrueras från haschet i 3,5 ms. De synliga strukturerna beror på bevarad samstämmighet. Detta översätts till snabbare åtkomst som granntrådar utföra liknande operationer och komma åt närliggande minne. (e) Grannstangenterna hålls samman under undersökningen, vilket förbättrar sammanhållningen i minnesåtkomsten till granntrådar. Nya rumsliga hashsystem har miljontals nycklar i parallella, kompakta glesa rumsliga data i små hashtabeller samtidigt som det fortfarande möjliggör snabb åtkomst från GPU. Tyvärr, tillgängliga system lider av två nackdelar: Flera körningar av byggprocessen krävs ofta innan framgång, och den slumpmässiga karaktären av hash funktioner minskar åtkomstprestanda. Vi inför ett nytt parallellt hashsystem som når hög belastningsfaktor med mycket låg felfrekvens. Dessutom har vårt system den unika fördelen att utnyttja samstämmighet i data och åtkomstmönster för snabbare prestanda. Jämfört med befintliga metoder, uppvisar den mycket större lokalitet av minnesåtkomst och konsekvent utförande vägar inom grupper av trådar. Detta är särskilt väl lämpat för datorgrafikapplikationer, där rumslig sammanhållning är vanligt förekommande. I brist på samstämmighet vårt system fungerar på samma sätt som tidigare metoder, men lider inte av byggfel. Vår plan är baserad på Robin Hood-systemet modifierat för att snabbt avbryta frågor om nycklar som inte finns i tabellen, och för att bevara samstämmigheten. Vi demonstrerar vårt system på en mängd olika dataset. Vi analyserar konstruktion och åtkomst prestanda, samt cache och trådar beteende.
García m.fl. REF förbättrar datakonsistensen och konstruktionshastigheten för rumslig hashning genom att använda sammanhängande hashfunktioner och parallellkonstruktion på en GPU.
Coherent parallel hashing
{'venue': "SA '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}