The Approaches of hash-memory efficiency increasing by lookup statistics usage

Alexsandr Markovskyy ¹, associated professor, PhD, & Alena Metlashevskaya ¹, post graduate student

1 Computer System Department, Faculty of Information and Computing Technique, National Technical University of Ukraine “Kyiv Polytechnic Institute”, Address: 37, Prospect Permohy, 03056, Kyiv-56, Ukraine, e-mail: alena@rpg-partners.com.ua

Key lookup is base operation at the decision of a wide class of the information processing tasks. The fastest program method of key lookup is hash-addressing. A necessary condition of hash-lookup efficiency under the complication of modern computer architecture is the account of features of their organisation. In particular, one of presence essentially affects on hash-lookup efficiency is multilevel memory organisations in modern computing systems. Accordingly, an actual problem is working out of the effective hash-lookup organisation in such systems.

The basic problem in realisation of any lookup technologies, such as hash-lookup, in systems with virtual memory is necessity of an overload of pages between memory levels. Therefore the important problem of hash-memory realisation in such systems is reductions of average and maximum number of pages overloads per lookup operations.

For increase of efficiency of hash-lookup in systems with virtual memory it is offered:

1. To place in cache-memory the keys copy which use is the most probable. That will allow reducing average time of hash-lookup;

2. To localise the collisions resolution within the one page of hash-memory so that by search in a key the overload no more than one page was required.

Technologically the first direction is offered to be realised as follows: in the allocated cache-area (area of duplicates), after each lookup operation, the key and associated data writes. Thus, the address in the area of duplicates is defined by separate hash-transformation. In case of collision occurrence the new key is placing to the area of duplicates with replacement of the old.

Key hash-lookup is carried out by following order. In the beginning hash-search in the area of duplicates is carried out. If the key is not found, the basic hash-address which first bits define number of page of hash-memory is calculated. If the page is absent in cache-memory its loading from the general memory. After page loading, hash-lookup is realised in it.

The basic problem of technological realisation of the second of the offered directions is possibility of page overflow (the number of keys with conterminous number of page exceeds admissible value). For the decision of this problem it is offered to limit length of a collisions chain. If at such restriction the key cannot be placed in hash-memory page, it placed in special area of cache-memory (overflow area). If during lookup in cache-memory there is no page corresponding to a key its loading from the general memory. Search of a key in the area of overflow is simultaneously carried out. If the key is found in overflow area, page loading interrupts. Otherwise, key hash-search in the loaded page is carried out.

In the report under the theoretical and experimental researches, recommendations about distribution of accessible volume of cache-memory between overflow area, area of duplicates and memory of the pages loaded from the general memory, are developed.

Software of the offered organisation of hash-lookup in systems with virtual memory is developed. Experimental approbation of the developed software has shown that speed of search increases by 30-40 %.