Доброго времени суток!
Задал мне препод задачку: отсортировать массив байтовых чисел с использованием MMX.
После нескольких часов упорного кодирования, я понял, что известные мне алгоритмы под эту задачу не подходят никоим образом, и, собственно, призадумался. Искал везде, вплоть до Яndexа, но — ничего.
Может есть какие-нибудь идеи?
Здравствуйте, IvanD, Вы писали:
ID>Доброго времени суток! ID>Задал мне препод задачку: отсортировать массив байтовых чисел с использованием MMX. ID>После нескольких часов упорного кодирования, я понял, что известные мне алгоритмы под эту задачу не подходят никоим образом, и, собственно, призадумался. Искал везде, вплоть до Яndexа, но — ничего. ID>Может есть какие-нибудь идеи?
хехе! наскоко я знаю тут без ассемблера не обойтись, потому как в С/C++/... компилятор должен уметь создавать MMX оптимизированный код и не имеет значения какие ты функции использовал. MSVC вроде умеет, но доказать это можно только после компановки и сборки используя disassembler или debugger. (и желательно знать ассемблерные команды, например movd — MMX команда для перемещения из регистра в регистр или в ячейку памяти). к сожалению другого пути не знаю.
Здравствуйте, Кирилл Осенков, Вы писали:
КО>А что ты имеешь ввиду
...известные мне алгоритмы под эту задачу не подходят никоим образом?
Не удается MMX прикрутить? Или как?
Дело в том, что MMX предоставляет возможность сравнивать сразу 8 байт (элементов массива), ну и пересылать между регистрами и памятью тоже по 8 байт, за счет этого и достигается оптимизация. Вопрос в том, как это реализовать, чтобы еще и массив сортировался.
Здравствуйте, iLmaR, Вы писали:
LR>хехе! наскоко я знаю тут без ассемблера не обойтись, потому как в С/C++/... компилятор должен уметь создавать MMX оптимизированный код и не имеет значения какие ты функции использовал.
Это я понимаю. Но преподу нужна не программа, которая быстро сортирует, а именно алгоритм, использующий MMX, а насчет ассемблера — согласен, хотя можно MMX-функции и на C++ использовать.
Здравствуйте, IvanD, Вы писали:
ID>Здравствуйте, Кирилл Осенков, Вы писали:
КО>>А что ты имеешь ввиду
...известные мне алгоритмы под эту задачу не подходят никоим образом?
Не удается MMX прикрутить? Или как?
ID>Дело в том, что MMX предоставляет возможность сравнивать сразу 8 байт (элементов массива), ну и пересылать между регистрами и памятью тоже по 8 байт, за счет этого и достигается оптимизация. Вопрос в том, как это реализовать, чтобы еще и массив сортировался.
Я не експерт по MMX и низкоуровневому кодингу, но, по-моему, MMX тут не поможет. Дело в том, что в задаче сортировки основную роль играют обращения к памяти, а им по барабану, какими инструкциями они делаются. Размер-то массива один и тот же!
Ну а если я все же не прав, то вот такая идея:
выровняй длину массива по 8, и представь, что это 8 массивов, вдвинутых друг в друга:
Здравствуйте, IvanD, Вы писали:
ID>Доброго времени суток! ID>Задал мне препод задачку: отсортировать массив байтовых чисел с использованием MMX. ID>После нескольких часов упорного кодирования, я понял, что известные мне алгоритмы под эту задачу не подходят никоим образом, и, собственно, призадумался. Искал везде, вплоть до Яndexа, но — ничего. ID>Может есть какие-нибудь идеи?
Для сортировки подсчетом у тебя есть несколько основных операций.
1. Обнуление массива(самы короткий этап) — это можно оптимизировать для MMX
2. Подсчет элементов — на счет этого не знаю, MMX уже не помню.
3. Заполнение массива в нужном порядке(самый долгий этам) — это тоже можно оптимизировать для MMX
Здравствуйте, Plutonia Experiment, Вы писали:
PE>Для сортировки подсчетом у тебя есть несколько основных операций.
PE>1. Обнуление массива(самы короткий этап) — это можно оптимизировать для MMX PE>2. Подсчет элементов — на счет этого не знаю, MMX уже не помню. PE>3. Заполнение массива в нужном порядке(самый долгий этам) — это тоже можно оптимизировать для MMX
Попробую. Кирилл Осенков (выше) уже упоминал об этом методе, признаюсь, раньше не приходилось с ним сталкиваться.
Спасибо за наводку!
Здравствуйте, Sinclair, Вы писали:
S>Ну а если я все же не прав, то вот такая идея: S>выровняй длину массива по 8, и представь, что это 8 массивов, вдвинутых друг в друга: S>
S>используй MMX для одновременной сортировки этих 8ми массивов, а потом слей их в один массив.
Это вроде похоже на метод Шелла? Но в нем, если мне не изменяет память, делается несколько проходов с разными шагами. Таким методом, возможно, массив частично отсортируется, но шаг все равно нужно менять => MMX бесполезен.
Здравствуйте, IvanD, Вы писали:
ID>Здравствуйте, Sinclair, Вы писали:
S>>Ну а если я все же не прав, то вот такая идея: S>>выровняй длину массива по 8, и представь, что это 8 массивов, вдвинутых друг в друга: S>>
S>>используй MMX для одновременной сортировки этих 8ми массивов, а потом слей их в один массив.
ID>Это вроде похоже на метод Шелла? Но в нем, если мне не изменяет память, делается несколько проходов с разными шагами. Таким методом, возможно, массив частично отсортируется, но шаг все равно нужно менять => MMX бесполезен.
Это больше на сортировку слиянием похоже. Только надо быстро находить минимум среди N/8 элементов. Для этого можно использовать структуру данных "куча".
Только в твоем случае все равно сортировка подсчетом быстрее будет.
Здравствуйте, IvanD, Вы писали:
ID>Здравствуйте, iLmaR, Вы писали:
LR>>хехе! наскоко я знаю тут без ассемблера не обойтись, потому как в С/C++/... компилятор должен уметь создавать MMX оптимизированный код и не имеет значения какие ты функции использовал.
ID>Это я понимаю. Но преподу нужна не программа, которая быстро сортирует, а именно алгоритм, использующий MMX, а насчет ассемблера — согласен, хотя можно MMX-функции и на C++ использовать.
