Форум программистов, компьютерный форум CyberForum.ru

Перемножение матриц 6000Х6000 - C++

Восстановить пароль Регистрация
 
Sanyur
11 / 11 / 0
Регистрация: 19.03.2010
Сообщений: 101
14.06.2012, 22:04     Перемножение матриц 6000Х6000 #1
Нужно перемножить матрицы размером в 6000 на одном ядре(один поток).
Рассчитать теоретическое время.

Кто-нибудь, подскажите пожалуйста: почему препод говорит, что время выполнения операции с плавающей точкой при частоте 2.5 GHz 10^10(процессоры вычисляют 4 операции с плавающей точкой одновременно, то есть 2.5*4*10^9) и почему он говорит, что в эту величину внесено время выборки из ОП.

В теории должно быть 500Х10^9 операций / 10^10 = 50 секунд.(Я так понимаю препод округлил 432=6*6*6*2)

На практике получается больше часа, если еще получится вычислить.

Почему такие различия в результатах?

компилятор vs2010, обычный проект с++, платформа х64.

алгоритм обычный(матрица здесь умножается на себя для экономии времени написания программы и памяти выделяемой в программе. как мне кажется если таким же способом перемножать разные матрицы время не уменьшится)
C++
1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 0; i< 6000; i++)
    {
        for(int j = 0; j< 6000; j++)
        {
            float buf = 0;
            for(int k = 0; k< 6000; k++)
            {
                buf += pfltMasA[6000*k+i]*pfltMasA[6000*j+k];
            }
            pfltMasC[j*6000+i] = buf;
        }
    }

Прошу сделать подсказки(или привести код) КАК обычным алгоритмом(без кеша и распараллеливания) получить 50с и/или обосновать почему получается такое ужасное время. Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.06.2012, 22:04     Перемножение матриц 6000Х6000
Посмотрите здесь:

C++ Перемножение матриц
Перемножение 2-ух матриц C++
Перемножение матриц. C++
Перемножение матриц C++
C++ Перемножение матриц
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nick Alte
Эксперт С++
1561 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
14.06.2012, 23:43     Перемножение матриц 6000Х6000 #2
50 секунд при таком описании - эльфийски-идеальный случай, когда производятся только операции умножения в правильной последовательности, чтобы процессор мог выполнять их одновременно по нескольку штук, а все данные волшебным образом появляются сразу в регистрах или на стеке FPU. С суровыми реалиями жизни и способами их преодоления поможет ознакомиться книга Криса Касперски "Техника оптимизации программ. Эффективное использование памяти.". Не сходя с места, сразу можно сказать, что чтение одной матрицы по строкам, а другой (или той же самой) по столбцам сразу внесёт живую и заполошную суматоху в работу процессорного кеша, приводящую к десяткам-сотням тактов ожидания чтения из памяти чуть ли не на каждом умножении.
Sanyur
11 / 11 / 0
Регистрация: 19.03.2010
Сообщений: 101
15.06.2012, 01:30  [ТС]     Перемножение матриц 6000Х6000 #3
прошу опровергнуть это:
Цитата Сообщение от Sanyur Посмотреть сообщение
500Х10^9 операций / 10^10 = 50 секунд
и это:
Цитата Сообщение от Sanyur Посмотреть сообщение
в эту величину внесено время выборки из ОП.
Да, действительно, знал фокус с транспонированием, но написал не подумав. дает 17 минут, или 1020с. Но это без учета транспонирования. (я так понимаю транспонирование имеет квадратную сложность, так что должно быть быстрее).
Но все же: в эту цифру(10^10)внесено ли время выборки случайного(заданного) значения из ОП или нет?
Так же прошу прощения:
Цитата Сообщение от Sanyur Посмотреть сообщение
время выполнения операции с плавающей точкой при частоте 2.5 GHz 10^10
Здесь имелась ввиду количество операций, время обратная величина.
Nick Alte
Эксперт С++
1561 / 982 / 115
Регистрация: 27.09.2009
Сообщений: 1,897
Завершенные тесты: 1
15.06.2012, 20:23     Перемножение матриц 6000Х6000 #4
Цитата Сообщение от Sanyur Посмотреть сообщение
в эту цифру(10^10)внесено ли время выборки случайного(заданного) значения из ОП или нет
Ну разумеется, не внесено. Это, как я и говорил, "идеально-эльфийский случай", когда процессор нон-стоп каждый такт выполняет по 4 операции с плавающей точкой. Это возможно только при выполнении целого ряда условий: последовательность команд и порядок следования операндов идеально подогнаны, а данные уже находятся под рукой. В реальной жизни едва ли можно ожидать первого, и в случае описанных матриц уж точно не приходится рассчитывать на второе.
Yandex
Объявления
15.06.2012, 20:23     Перемножение матриц 6000Х6000
Ответ Создать тему
Опции темы

Текущее время: 15:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru