Project

General

Profile

Forums » Программное обеспечение »

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

Added by sprin about 11 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

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

mc_POPCNT32.7z (2.01 KB) mc_POPCNT32.7z
mc_POPCNT64.7z (2.77 KB) mc_POPCNT64.7z
mc_POPCNT32_01.png (5.8 KB) mc_POPCNT32_01.png
mc_POPCNT32_02.png (8.27 KB) mc_POPCNT32_02.png
mc_POPCNT64_01.png (7.08 KB) mc_POPCNT64_01.png
mc_POPCNT64_02.png (10.9 KB) mc_POPCNT64_02.png

Replies (51)

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

Aha wrote:

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

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

(51-51/51)