Project

General

Profile

Ассемблер. Реализация POPCNT для MC P1

Added by sprin over 10 years ago

Здравствуйте.

Решил реализовать для MC P1 алгоритм реализации команды POPCNT, которая может быть использована для эффективного поиска в огромном объёме данных.
Она работает посредством подсчета количества бит множества в объекте данных.
Пример приложений, которые получат преимущества от использования этой инструкции: выявление генома, распознавание почерка, медицина и быстрое вычисление хэмминговского расстояния и заполнения.

Ресурсы:

программно-ориентированные ускорители (набор команд)
SSE4 - Википедия
chessprogramming.wikispaces.com собраны основные алгоритмы и ссылки по теме POPCNT.
Benchmarking CRC32 and PopCnt instructions


Алгоритмы реализовал (с учётом возможностей MC P1) по 4 варианта для входных значений размерностью 32 бит и 64 бит.

mc_POPCNT32_v1, mc_POPCNT64_v1 - The PopCount routine
mc_POPCNT32_v2, mc_POPCNT64_v2 - Lookup (Подстановка из таблицы на 256 элементов готовых значений)
mc_POPCNT32_v3, mc_POPCNT64_v3(+b) - Lookup (Подстановка из таблицы на 256 элементов готовых значений)
mc_POPCNT32_v4, mc_POPCNT64_v4 - HAKMEM 169


В теории, если все команды будут выполняться за 1 такт, то можно посчитать минимальное время выполнения функции, что я и сделал:

Графики (если все команды будут выполняться за 1 такт)

Show


На практике результаты не проверялись.


Replies (51)

RE: Ассемблер. Реализация POPCNT для MC P1 - Added by VaalKIA over 8 years ago

Aha wrote:

Оптимистичнее стоит быть, а то с таким настроением мы устройств в широкой продаже на мультиклете не дождемся :-(

Ну а я думаю, что всего лишь надо отслеживать как происходит развитие этой аппаратуры по миллиону баксов за штуку, да и насчёт библиотек уже можно побеспокоиться, ведь те кто будет покупать оборудование не сами их будут писать, значит они вместе с оборудованием наверняка идут, и значит они уже есть и про них уже можно начать выяснять - что это и как. А про 2016 год.. ну так он уже почти наступил и 32нм в 2016, это не то же самое, что 90нм в ближайшие несколько лет.
И я думаю, что сам характер производства на таких агрегатах, позволяет каждую новую пластину делать уникальную, поэтому пропихнуть мелкие заказы на фоне одного большого - никаких проблем не составит: это же режим цифровой типографии (если бы они заворачивали всех клиентов, пока какой-нить большой заказ жуётся, клиентов у них бы не осталось очень быстро)

(51-51/51)