Intel® Moderncode for Parallel Architectures
Support for developing parallel programming applications on Intel® Architecture.

bin hopping algorithm

Biswabandan_Panda
616 Views
where i can get the entire algorithm for bin hopping?
0 Kudos
2 Replies
Biswabandan_Panda
616 Views
i did not get u,but as i know
Bin hopping optimizes the virtual-to-physical map-ping for accesses that target repeated sequences of vir- tual memory locations. In practice, consecutively al- located physical pages that support consecutively allo- cated virtual pages are selected not to collide in the. Bin hopping therefore exploits temporal locality of applications.

0 Kudos
ClayB
New Contributor I
616 Views
You found the same online paper that I did. It doesn't have an algorithm, as you've found.

Have you tried the reference [12] cited in the paper?

Kessler, R.E., Hill, M.D.: Page placement algorithms for large real-indexed caches. ACM Trans. Comput. Syst. 10 (1992) 338359.

From "An Empirical Study of the Effects of Careful Page Placement in Linux" by Bahadur, et al (http://portal.acm.org/ft_gateway.cfm?id=275365&type=pdf), I found this:

In dynamic coloring, bin selection is based upon some dynamic estimate of each bins activity level. Without special hardware such as that proposed in [J. Baker. The Effects of Virtual Page Placement on Cache Miss Ratios. M.S. Thesis, Department of Computer Science, Clemson University, Clemson SC, 1992], accurate estimates may be impossible to obtain. The principle of temporal locality indicates that a bin that has been recently assigned a new page is likely to experience relatively high activity. This observation motivates the round robin assignment of bins which is commonly known as bin hopping. Two variations of bin hopping have been studied and reported upon: global bin hopping in which the page fault manager simply maintains a single next-bin identifier and local bin hopping in which a next-bin identifier is maintained for each process.


I would also suggest trying texts on virtural memory systems.

--clay
0 Kudos
Reply