| |
 Матрица 8х8 - как заменить столбцы строками ?, требуется БЫСТРЫЙ алгоритм обработки |
|
|
|
|
 Mar 10 2008, 12:36
|
Участник
Группа: Участник
Сообщений: 34
Регистрация: 21-09-04
Пользователь №: 688
|
Реальная задача для контроллера Мega128 (CVAVR): есть две матрицы 8х8 бит - два массива по 8 байт Код // здесь какждый байт массива представляет собой столбец матрицы
char Vbuf[1][8] = {... типа данные};
// а этом случае каждый байт массива - это строка
char Hbuf[8][1] = {... типа данные};
в общем данные хранятся примерно так ...
Vbuf[1][8]; Hbuf[8][1];
0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7
1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7
2 2 2 2 2 2 2 2 0 1 2 3 4 5 6 7
3 3 3 3 3 3 3 3 0 1 2 3 4 5 6 7
4 4 4 4 4 4 4 4 0 1 2 3 4 5 6 7
5 5 5 5 5 5 5 5 0 1 2 3 4 5 6 7
6 6 6 6 6 6 6 6 0 1 2 3 4 5 6 7
7 7 7 7 7 7 7 7 0 1 2 3 4 5 6 7
т.е. первый байт Vbuf представляет собой 0-ые биты каждого байта Hbuf
второй байт Vbuf представляет собой 1-ые биты каждого байта Hbuf и т.д.... Требуется преобразовать матрицу Vbuf в Hbuf. Простейшее решение - побитовое копирование. В это случае контроллер должен будет сделать (8х8)*(команды извлечения бита + команды копирования бита + куча команд для формиро циклов) операций. В итоге получается АЦКАЯ работа. В моем случае таких матриц к примеру 80 и обработка занимает порядка 50мс. Хотелось бы услышать дельные советы бывалых программеров о том как оптимизировать алгоритм (мега тактируестя 20МГц и менять ее на что-то более мощное не возможности). Может стоит по другому организовать хранение данных или есть типовые алгоритмы. Буду рад услышать любой совет !!!!
|
|
|
|
|
|
|
|
Mar 10 2008, 13:01
|
Йа моск ;)
Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610
|
Алгоритм то есть. Не факт, правда, что на AVR он будет быстрее чем копирование битов, хотя можно попробовать. Готового исходника у меня под рукой нет, но основную идею постараюсь обрисовать. Есть 8 байт, сперва необходимо провернуть по биту Код 76543210 - 1й байт
HGFEDCBA - 2й байт
76543210 - 3й байт
HGFEDCBA - 4й байт
76543210 - 5й байт
HGFEDCBA - 6й байт
76543210 - 7й байт
HGFEDCBA - 8й байт нужно изготовить Код 6G4E2C0A
7H5F3D1B
6G4E2C0A
7H5F3D1B
6G4E2C0A
7H5F3D1B
6G4E2C0A
7H5F3D1B Следующая стадия - проворот по 2 бита, следующая - по четыре. Обрисую результат стадии поворота по 2 бита (участвуют по 4 байта), одна цифра - 2 бита: Код 3210
7654
DCBA
HGFE -> Код 2C0A
6G4E
3D1B
7H5F и последний поворот по 4 бита Код 10
32 -> Код 02
13
--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
|
|
|
|
|
|
|
|
Mar 10 2008, 14:35
|
Ambidexter
Группа: Свой
Сообщений: 1 589
Регистрация: 22-06-06
Из: Oxford, UK
Пользователь №: 18 282
|
Цитата(french @ Mar 10 2008, 12:36)  Реальная задача для контроллера Мega128 (CVAVR): есть две матрицы 8х8 бит - два массива по 8 байт
...
т.е. первый байт Vbuf представляет собой 0-ые биты каждого байта Hbuf, второй байт Vbuf представляет собой 1-ые биты каждого байта Hbuf и т.д. Требуется преобразовать матрицу Vbuf в Hbuf.
Простейшее решение - побитовое копирование.
В это случае контроллер должен будет сделать (8х8)*(команды извлечения бита + команды копирования бита + куча команд для формиро циклов) операций. В итоге получается АЦКАЯ работа.
В моем случае таких матриц к примеру 80 и обработка занимает порядка 50мс.
Хотелось бы услышать дельные советы бывалых программеров о том как оптимизировать алгоритм (мега тактируестя 20МГц и менять ее на что-то более мощное нет возможности). Может стоит по другому организовать хранение данных или есть типовые алгоритмы. Буду рад услышать любой совет !!!! Разместите 8 байт вашего Vbuf в регистрах r0-r7 и делайте побитное копирование, например, вызывая такую подпрограмму: Код getHbyte:
ror r0
ror r8
ror r1
ror r8
ror r2
ror r8
ror r3
ror r8
ror r4
ror r8
ror r5
ror r8
ror r6
ror r8
ror r7
ror r8 ;готов n-й байт Hbuf
ret забираете готовый байт и повторяете ещё 7 раз. На один байт уйдёт 23МЦ, на одну конвертацию вгрубе уйдёт всего 8*23*0.05=9.2 мкс, на 80 уйдёт 80*9.2=736 мкс, откуда 50 мс?
--------------------
Делай сразу хорошо, плохо само получится
|
|
|
|
|
|
|
|
Mar 10 2008, 21:02
|
Местный
Группа: Свой
Сообщений: 208
Регистрация: 6-07-04
Из: Полтава
Пользователь №: 279
|
Транспонирование матрицы битов: Код b0 b1 b2 b3 b4 b5 b6 b7 b0 b1 b2 b3 b4 b5 b6 b7
r0 00 01 02 03 04 05 06 07 r8 00 10 20 30 40 50 60 70
r1 10 11 12 13 14 15 16 17 r9 01 11 21 31 41 51 60 71
r2 20 21 22 23 24 25 26 27 r10 02 12 22 32 42 52 62 72
r3 30 31 32 33 34 35 36 37 r11 03 13 23 33 43 53 63 73
r4 40 41 42 43 44 45 46 47 r12 04 14 24 34 44 54 64 74
r5 50 51 52 53 54 55 56 57 r13 05 15 25 35 45 55 65 75
r6 60 61 62 63 64 65 66 67 r14 06 16 26 36 46 56 66 76
r7 70 71 72 73 74 75 76 77 r15 07 17 27 37 47 57 67 77 Простой вариант "в лоб". Исходная помещается в r0-r7, результирующая получается в r8-r15: Код movw r8,r0
mowv r10,r2
movw r12,r4
movw r14,r6
bst r0,1
bld r9,0 // из 01 перенесено в 10 другой матрицы
bst r1,0
bld r8,1 // из 10 перенесено в 01 другой матрицы
...
bst r6,7
bld r15,6 // из 67 перенесено в 76 другой матрицы
bst r7,6
bld r14,7 // из 76 перенесено в 67 другой матрицы Всего необходимо 28 взаимных пересылок, что в результате занимает 28х4=112 тактов. Плюс 4 такта копирования регистровых пар, получается 116 тактов. Итого транспонирование матрицы битов занимает по времени 5,8 мкс. Для 80 матриц - 464 мкс, с накладыми расходами пусть будет ~0,5 мс, т.е. в 100 раз быстрее, чем у Вас получилось. PS: Сейчас не вспомню, но существует более быстый способ транспонирования, дающий экономию еще около 20% времени.
|
|
|
|
|
|
|
|
Mar 11 2008, 08:13
|
Знающий
Группа: Свой
Сообщений: 771
Регистрация: 16-07-07
Из: Волгодонск
Пользователь №: 29 153
|
А вариант Код #define TESTBIT(v, n) ( (v>>n) & 1)
char buf[8] = {... типа данные};
#define Vbuf(x,y) TESTBIT(buf[x], y)
#define Hbuf(x,y) TESTBIT(buf[y], x) чем не устраивает?
|
|
|
|
|
|
|
|
Mar 11 2008, 09:13
|
Участник
Группа: Участник
Сообщений: 34
Регистрация: 21-09-04
Пользователь №: 688
|
Правильно задать вопрос - пол проблемы решить !!! Чтобы не путать уважаемою аудиторию постараюсь яснее изложить мою проблему: Есть два массива по 8 байт (а в реале размер кратен 8) unsigned char Vbuf[8]; unsigned char Hbuf[8]; пусть Vbuf будет таким: 12345678 - 1-й байт ABCDEFGH - 2-й байт 87654321 - 3-й байт abcdefgh - 4-й байт QWERTYUI - 5-й байт qwertyui - 6-й байт ASDFGHJK - 7-й байт asdfghjk - 8-й байт надо скопировать в Hbuf так чтобы в нем 1A8aQqAa - 1-й байт 2B7bWwSs - 2-й байт 3C6cEeDd - 3-й байт 4D5dRrFf - 4-й байт 5e4eTtGg - 5-й байт 6F3fYyHh - 6-й байт 7G2gUuJj - 7-й байт 8H1hIiKk - 8-й байт решение задачи в лоб (побитовое копирование) выглядит так: Код #define _HEIGHT 16 // высота экрана в строках (битах)
#define _WIDTH 4 // ширина экрана кратная 1 байту
#define _H _HEIGHT/8
#define _W _WIDTH*8
unsigned char SCREEN2[_HEIGHT][_WIDTH]; // буфер видео-памяти (G-формат)
unsigned char BUFFER [_H][_W]; // рабочий буфер видео-памяти (V-формат)
unsigned char ws_i=0, wb_i=0, hsi_bit=0, hs_i=0, hs_byte=0;
// преобразование данных из вертикального формата
// в горизонталный
for(ws_i=0; ws_i<_WIDTH; ws_i++)
{
for(hs_i=0; hs_i<_HEIGHT; hs_i++)
{
if(hsi_bit > 7) {hsi_bit=0; hs_byte++;}
for(wb_i=0; wb_i<8; wb_i++)
SCREEN[hs_i][ws_i] |= (((unsigned char)BUFFER[hs_byte][(unsigned int)(wb_i+ 8*ws_i)]>>hsi_bit)<<7)>>wb_i; // собственно побитовое копирование !!!
hsi_bit++;
}
hs_byte=0;
hsi_bit=0;
} эта штука работает, но долго !!! Цитата Простой вариант "в лоб".
Исходная помещается в r0-r7, результирующая получается в r8-r15:
movw r8,r0
mowv r10,r2
movw r12,r4
movw r14,r6
bst r0,1
bld r9,0 // из 01 перенесено в 10 другой матрицы
bst r1,0
bld r8,1 // из 10 перенесено в 01 другой матрицы
...
bst r6,7
bld r15,6 // из 67 перенесено в 76 другой матрицы
bst r7,6
bld r14,7 // из 76 перенесено в 67 другой матрицы
Всего необходимо 28 взаимных пересылок, что в результате занимает 28х4=112 тактов. Плюс 4 такта копирования регистровых пар, получается 116 тактов. Итого транспонирование матрицы битов занимает по времени 5,8 мкс. Для 80 матриц - 464 мкс, с накладыми расходами пусть будет ~0,5 мс, т.е. в 100 раз быстрее, чем у Вас получилось. класс, но пишу на Си, регистры все заняты компилятором !!! можно конечно сохранять их значения а потом восстанавливать, но 16 регистров.... помоему не реально.
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
По условию задачи было не 8х8 байт, а 8х8 бит. Вроде так. 
