>Заметим, что задача очень похожа на типичный базоданновый поиск, только вместо диска у нас - медленная глобальная память (но суть та же - позиционирование медленное, чтение-запись быстрые), а вместо кэша в просто памяти - кэш в быстрой памяти (shared/регистры). Ничто не ново под луною.

Как раз сегодня смотрел незабвенного Кнута, 3т. Там была описана работа с внешней памятью (магнитной лентой) при сортировке. Вопрос меня заинтересовал как раз в связи с проблемой глобальной - шеред памяти в куда. Но ничего особенного не вынес. У Кнута это все вариации на тему mergesort. Это мало пригодно для многопроцессорных систем.