Всем привет! Я решил рассказать вам о том, как оптимизировал алгоритм майнинга лайткоинов. А представлю я свой рассказ в форме дневника.
День 0: Наткнулся на топик, где некий bitless поделился с сообществом способом ускорить майнинг на несколько процентов. Спросил себя: чем я хуже него? Приступил к анализу кода.
День 1: Вспоминаю синтаксис, нахожу информацию о функциях OpenCL'а.
День 2: Наткнулся на очень странные строчки кода:
#define Coord(x,y,z) x+y*(x ## SIZE)+z*(y ## SIZE)*(x ## SIZE)
#define CO Coord(z,x,y)
Подставил первую сточку во вторую, получил
#define CO z+x*zSIZE+y*xSIZE*zSIZE
Зачем было городить огород — мне не понятно, к тому-же в функции scrypt_core нашлась неиспользуемая переменная ySIZE.
Так же в функции search нашел многократные использования i*2, заменил на rotl(i,1U). Прироста производительности это не дало, но пусть будет.
День 3: Понял, что мой единственный шанс что-то оптимизировать, при текущем уровне знаний — помочь компилятору с «CO», ведь при настройках по умолчанию, z+x*zSIZE+y*xSIZE*zSIZE считается 8704 раза. Скорее всего, компилятор как-то оптимизирует эти вычисления, но это не мешает ему немножко помочь :) К тому-же zSIZE — константа, равная 8, а xSIZE — константа, получаемая из настроек программы.
Начал исследовать первый цикл, в котором используется «CO»:
for(uint y=0; y<1024/LOOKUP_GAP; ++y)
{
#pragma unroll
for(uint z=0; z<zSIZE; ++z)
lookup[CO] = X[z];
//далее неинтересный мне код
}
Видно, что x*zSIZE — константа, поскольку x не меняется в ходе выполнения цикла. Так же очевидно, что y увеличивается на 1 с каждой итерацией цикла.
Понимая это, напрашивается создание переменной CO, в которой изначально будет хранится x*zSIZE, а с каждой итерацией цикла, в нее будет добавляться xSIZE*zSIZE.
А, чтобы переменная z нам не мешала, создадим внутри цикла локальную переменную, к которой и будем прибавлять по единице после каждой итерации внутреннего цикла.
Помимо вышеозначенной причины, это может позволить компилятору запихнуть эту переменную в регистр, что тоже должно ускорить процесс.
В итоге получился следующий код:
uint CO=rotl(x,3U);// x*zSIZE
uint CO_tmp=rotl(xSIZE,3U);//xSIZE*zSIZE
for(uint y=0; y<1024/LOOKUP_GAP; ++y, CO+=CO_tmp)
{
uint CO_reg=CO;
#pragma unroll
for(uint z=0; z<zSIZE; ++z, ++CO_reg)
lookup[CO_reg] = X[z];
//далее неинтересный мне код
}
День 4: Анализирую следующие использования «CO». Код в препроцессоре пропускаю, поскольку там оно используется только один раз.
for (uint i=0; i<1024; ++i)
{
uint4 V[8];
uint j = X[7].x & K[85];//K[85]=0x000003FFU
uint y = (j/LOOKUP_GAP);
#pragma unroll
for(uint z=0; z<zSIZE; ++z)
V[z] = lookup[CO];
//далее неинтересный мне код
}
Видно, что y меняется по довольно сложному алгоритму, предугадать значение этой переменной получится вряд ли.
Поэтому все, что я могу — посчитать заранее x*zSIZE и xSIZE*zSIZE.
CO_tmp=rotl(x,3U);
CO=rotl(xSIZE,3U);
for (uint i=0; i<1024; ++i)
{
uint4 V[8];
uint j = X[7].x & K[85];
uint y = (j/LOOKUP_GAP);
uint CO_reg=CO_tmp+CO*y;
for(uint z=0; z<zSIZE; ++z, ++CO_reg)
V[z] = lookup[CO_reg];
//далее неинтересный мне код
}
День 5: Компилирую, и наблюдаю прирост на своей конфигурации ~3%. Перепроверив результаты несколько раз, привожу код в человеческий вид, оптимизирую код в препроцессорном участке так же, как во втором цикле, и убираю ранее сделанную замену i*2 на rotl(i,1U).
После тестов «очищенного» кода результат меня удивляет — скорость стала существенно меньше, чем до начала моей оптимизации. Проведя небольшое расследование, я выяснил, что причина этому — возвращение обратно i*2, вместо rotl(i,1U).
Казалось-бы, сама замена ничего не дает вообще ничего — проверял несколько раз, однако вместе с моими оптимизациями — увеличивает скорость.
Отправляю результаты моих трудов на почту Con Colivas'у.
День 12: Не дождавшись ответа в течение недели, выкладываю свои достижения и инструкции на официальный форум лайткоинов.
С несколькими людьми это сработало и действительно дало прирост скорости. Однако, в скором времени обнаружилась проблема — я проводил тесты с драйверами 13.4, а с более ранними версиями драйверов(и OpenCl) — скорость падает примерно на треть.
Поставил себе драйвера 13.1 (не без проблем — версия OpenCl понижаться не хотела вплоть до полной очистки системы от драйверов AMD и OpenCL), начинаю исследования.
День 13: Обнаружил, что падение производительности вызывает та самая загадочная замена i*2 на rotl(i,1U). Но, убрав эту замену, скорость возвращается на начальный уровень.
Понимаю, что придется делать две версии оптимизаций: для 13.4, и для более старых версий драйверов.
Дни 13-40: Набрав себе добровольных тестеров, из числа тех, кто сообщал о неработающей оптимизации на 13.1 — начинаю работу.
В ходе тестов обнаруживаются железозависимые оптимизации, от которых я сразу отказываюсь(к таким относится, например, создание массива на 1024 элемента, в которых хранятся предпосчитанные значения y*xSIZE*zSIZE, для y=0..1023 — у меня оптимизация заработала, у тестеров нет), а так же нелинейное влияние частот на результаты некоторых оптимизаций: на моей 7850 при частотах 1000/1300, выдавались аномальные результаты, вроде ~340 килохешей в секунду при интенсивности 13(позволяет спокойно работать за компьютером, без подлагиваний в то время, когда видеокарта майнит), вместо ~200 килохешей в секунду без моей оптимизации и/или на других частотах.
Но, от таких оптимизаций пришлось отказаться(почти, для себя эту версию я сохранил).
Так же обнаружилось «магическое значение» настройки --thread-concurency, при которой скорость растет, равное 2^n+1, например 4097 или 16385. При любом другом значении скорость майнинга меньше.
Мои предположения — возможно, что умножение на 2^n+1 выполняется быстрее всего, но это не совсем логично, ведь умножение на 2^n — это простой битовый сдвиг влево, и, по идее, должен выполняться быстрее…
В итоге я пришел к следующему коду:
uint CO_tmp=xSIZE<<3U;//xSIZE*zSIZE
uint CO_tmp2=x<<3U;//x*zSIZE
for(uint y=0; y<1024/LOOKUP_GAP; ++y)
{
uint CO=y*CO_tmp+CO_tmp2;
#pragma unroll
for(uint z=0; z<zSIZE; ++z,++CO)
lookup[CO] = X[z];
//далее неинтересный мне код
}
//неизменный код
for (uint i=0; i<1024; ++i)
{
uint4 V[8];
uint j = X[7].x & K[85];
uint y = (j/LOOKUP_GAP);
uint CO=y*CO_tmp+CO_tmp2;
#pragma unroll
for(uint z=0; z<zSIZE; ++z)
V[z] = lookup[CO+z];
//далее неинтересный мне код
}
Опубликовал версию для драйверов старее, чем 13.4 на том-же форуме, упомянул про «магическое значение» —thread-concurency. И счел свою работу завершенной.
Надеюсь, что знающие люди смогут рассказать мне, что происходит при замене i*2 на rotl(i,1U), а так же природу «магического значения» параметра --thread-concurency.
Мой топик на форуме лайткоинов: forum.litecoin.net/index.php?topic=4082.0
P.S. все работы велись в файле scrypt.cl, входящем в комплект к любому майнеру, поддерживающему майнинг лайткоинов.
Автор: Bazanra
