Прирост производительности на SMP

А обмен с дисками есть?

Обмена сдисками нет памяти слава богу пока хватает 128Mb

А каким образом нитки общаются? Через общую память, обложенную мутексами?

Блокировки используются только один раз - для определения номера потока (единственная общая переменная для потоков, которая требует синхронизации). Насколько я понимаю общаюсь с физиком. Может быть более подрбно остано виться на задаче. Проблема то простая: нужно перемножить две матрицы. Первый поток считает первую строку, второй - вторую и т.д. Общими конечно являются массивы в которых храняться матрицы но доступ к ним (к массивам) асинхронный. Так что, как мне кажется, на синхронизацию времени не тратится.

Хм... Тогда, скорее всего, действительно железо. Больше некому. К сожалению, тут сейчас заведомо нормальная SMP-машинка сильно загружена, и результаты могут быть непоказатильными, но на двух тредах я добился ускорения на 185%. Чуть позже тут же кину ссылку на результат эксперимента (надо методику точной оценки в условиях загруженности придумать), для двух, трех и четырех процессоров. Железка - AlphaServer8200 5/625, ОС - Digital Unix5.0.

Ну тягаться с такой тачкой как у вас у меня нет ни какой возможности (шина памяти наверняка не 100Mhz). Я тут немного поэксперементировал и вот что получилось. Если просто тупо взять и выполнить 10^9 умножений двух чисел : с += a*b (именно эта операция доминирует при вычислении призведения матриц) результат вроде бы очень нечего ~5сек. на одном потоке. А если честно завести матрицы a[1000][1000], b[1000][1000], c[1000][1000] то время сразу же подскакивает до 25 сек. Напрашивается вывод - основное время тратится не на вычисление а на расчет адреса элементов матрицы либо память не успевает за процессорами. А я тут собрался Cooper'ы по 650Mhz ставить, а есть ли толк ?

Я может быть не совсем в тему пишу, но я как-то слышал, что замедление может быть из-за того, что у обоих процессоров в cache находится та же область памяти, и поэтому большинство времени процессоры дергаются из-за этого - когда один запишет, второй должен кеш обновить из памяти. Когда сделаешь матрицы побольше, то разные строки матрицы будут в cache у разных процессоров и всё будет в порядке.

For Justme: Можно попробовать как вариант я сам не знаю на счет организации cache-памяти прцессора, точнее на счет того что там седит. Но размер матрицы и так не маленький 8Мб каждая. А есть ли такая возможность сказать процессору что именно эта область памяти должна сидеть в cache?

Действительно, проблема может быть в том, что обращение идет к одной области памяти, и если перемножать параллельно РАЗНЫЕ матрицы, то возможно будет быстрее... P.S. Результатов эксперимента пока нет: жду профилактики, чтоб подсуетиться и протестировать пустую машину.

Я в СМП не эксперт, я это про кеш просто слышал на одной лекции.
Если программа - на С, то попробуй переделать алгоритм так, чтобы каждый поток считал свою _колонку_ матрицы (а не строчку) - может быть замедление связано с тем, как располагаются в памяти массивы в С (по колонкам, не по строчкам). Тогда оба потока не должны будут друг другу мешать.
Насчет указания процессору, что он должен держать в кеше - не знаю, но сам лично думаю, что это нельзя. Надо смотреть PDF от Интела.

Напрашивается алгоритм блочного перемножения матриц, он уже реализован ребятами из-за бугра и они вроде говорят что это наиболее эффективный метод. Хотя вы меня навели на кое-какие мысли. У меня при перемножении первый поток берет нечетные строки из первой матрицы и ВСЕ столбцы из второй, второй поток - четные строки из первой матрицы и опять ВСЕ столбцы из второй здесь и происходит обращение к одной области памяти. Вроде бы даже есть некая взаимосвязь - рост производительности на 50% <-> двойное обращение к одной и той же области памяти. Попробую организовать 4 потока- нечетные строки-нечетные столбцы, нечетные строки-четные столбцы, четные-нечетные и четные-четные. Правда небольшая загвоздочка - процессоров то всего два. Если не чего не поможет (а я это чувствую) придется писать методом блочного перемножения. Нсчет организации матрицы. Матрица - это класс C++ поэтому я могу хранить ее и по строкам и по столбцам (я храню ее построкам) это не имеет ни какой разницы. Строка (столбец) - это обычный массив.

Пре-скриптум: Что-то линукс.орг.ру не нравится мой HTML (квадратные скобки?), поэтому посылаю как есть. Надеюсь, что читабельность не пострадает очень сильно.
Дело не в том, из какой области памяти ты читаешь, а в том, в какую область памяти <I>записываешь</I> (по крайней мере, мне так кажется).<BR>
Я не знаю, что ты имеешь в виду под классом С++, но если ты хранишь сами элементы как, например, float a[1000][1000], то матрица хранится так:<BR>
<TT>
a[0][0], a[1][0], a[2][0], ..., a[999][0], a[0][1], ...
</TT>
то есть, если оба потока записывают что-то в одну и ту же колонку матрицы, то это идет в соседние ячейки памяти.<BR>
Не мог бы ты сюда вписать свой алгоритм и определение С++ класса матрицы (или он секретный ;-)?

Если несколько упростить (с точки зрения реализации на компьютере)
то матрица - double **a;
a = new *double[rows];
for(int i = 0; i < rows; ++i)
a[i] = new double[cols];
rows - количество строк; cols - количество столбцов; как видно матрица
хранится по-строчно т.е. обращение к элементу есть a[строка][столбец].

И второе - перемножение матриц:

сначала транспонируем матрицу b, так как вытаскивать столбец дольше
чем строку, - строки переходят в столбцы, столбцы в строки.

int thr_idx - номер потока (0,1,2,...)
for(int i = thr_idx; i < rows; i += MAX_THREADS)
for(j = 0; j < cols; ++j)
c[i][j] = a[i]*b[j];
Как видно каждый поток расчитывает только свой набор строк. Записи
со стороны обоих потоков в соседние ячейки памяти нет. Есть только
чтение из общей памяти - из матрицы b. Пробывал чтобы каждый поток
работал со своей матрицей b производительность только упала а объем
используемой памяти вырос на два размера матрицы (+16Мб). Я уже начал
однозначно склоняться к мысли что действительно пропускной способности
памяти (800Мб/сек) для двупроцессорной машины явно не хватает.

Хмм, а если перемножать целые числа (unsigned int), производительность повышается?

Я думаю вот что: надо сделать так, чтобы один поток вычислял верхнюю половину матрицы, а другой - нижнюю (но никак через строчку или столбец). Это дико увеличивает вероятность того, что камни не будут писать в смежную область памяти. Ну а по-хорошему, для таких вещей надо использовать пакет blas (а конкрентнее - его реализацию atlas) - там _очень_ умные буржуи все такие матричные алгоритмы реализовали на асме, с оптимизацией под конкретный тип камня (есть версии под x86 и alpha, может еще под че-то, но не уверен) (хотя есть вероятность, что atlas - не многопоточная вещь). А насчет управления кешем - я не уверен, но мне кажется что /proc/mttr на линуксе - это способ управления кешированием на камне (по-крайне мере я слышал, что можно убыстрить работу видюхи если на виртуальный адрес, куда отмаплена видеопамять, настроить один из регистров mttr). Ищите в google про оба случая. Пожалуйста, сообщите сюда результаты после того, как попробуете что-нибудь.

Вопрос : Что такое смежная область памяти ? Если это две ячейки типа double (int, char, ...) расположенные в одной области памяти выделенной посредством new (malloc, calloc, ...) то в таком случае записи в смежные области нет так как каждый поток пишет ТОЛЬКО в свои строки которые есть a[i] = new double[cols]. Если смежная память это что-то другое - поясните. for justme: с целочисленными аргументами не баловался, попробую позже. По-моему сказывается гнилость Intel'овской архитектуры, вроде бы GPL+ называется. А vsl куда-то пропал, а у него вроде Alpha есть. Если и там такая же борода то надо смотреть алгоритм, если там все нормально то, ... Ну сами понимаете.

Насчет смежных областей памяти: ну вы мыслите прям как ученый :) Не забывайте, что у PIII на кристале кеш второго уровня размером 256K-512K - так что не то чтоб ячейки не должны быть смежными - желательно чтобы элементы матрицы были в разных мегабайтах. А насчет atlas - попробуйте все-таки его (он еще есть на PPC помимо alpha и x86) - повышение произвродительности 3-8 раз по сравнению с С-шным кодом (хотя наверно придется юзать ихние структуры данных).

эй народ а вы как проги то компилировали ?
попробуйте между делом cc -On prog.cc (n=2...7)
енто оптимизация

да кстати такой прирост произв (не в 2 р) обьясняется тем что два процессора из одной памяти нехило тягают, когда там и одному то несвободно

Программа компилируется g++ -Wall -lpthread -O2 *cc -o x
Поэксперементировал тут немного.
Cтруктура класса Matrix.
class svtRMatrix {
private:
int m, n; // m - number of rows in matrix
// n - number of columns in matrix
svtStorage<svtRVector> a; // matrix rows

svtRMatrix Gauss(svtRMatrix &);

public:
svtRMatrix();
svtRMatrix(int, int);
svtRMatrix(const svtRMatrix &);

svtRMatrix &operator=(const svtRMatrix &);
svtRVector &operator[](int);

svtRMatrix operator+(const svtRMatrix &);
svtRMatrix &operator+=(const svtRMatrix &);
...
Ну и еще операторы
}

svtStorage - хранилище на базе массива указателей
В данном случае там хранятся вектор-строки (svtRVector)

Когда я при вычислении произведения матриц занашу результат в
обучную переменную типа double (результирующая матрица теряется)
double c;
for(int i = thread_index; i < rows; i += MAX_THREADS) {
for(int j = 0; j < cols; ++j) {
с = A->a[i]*B->a[j];
}
}

Производительность не меняется. Как только я сделал скалярное
произведение векторов A->a[i]*B->a[j] inline-функцией скорострельность
возросла в 5-6 раз. На радостях я стал записывать результат в матрицу:

for(int i = thread_index; i < rows; i += MAX_THREADS) {
for(int j = 0; j < cols; ++j) {
C->a[i][j] = A->a[i]*B->a[j];
}
}

И что ? Производительность стала ниже чем когда скалярное произведение
не inline-функция.
Народ ! Я что-то не так понимаю ?

Hi. Есть такая штука ,специально заточенная под матрицы - называется ATLAS (тоже самое , что и BLAS, но намного быстрее). При установке оптимизируется под конкретный процессор. Может лучше разобраться как работать с этой библиотекой , чем .... Смотри www.netlib.org/atlas

Ssory za mysor...

A tebe slychaino ne nado chtoto peredelat 
naprimer tak 


for(int i = thread_index; i < rows; i += MAX_THREADS) { 
for(int j = 0; j < cols; ++j) { 
C->a[i]->[j] = A->a[i]->[j]*B->a[i]->[j]; 
} 
} 

Escho raz ssory esli ya chego ne ponal ....no po idee...

							kred.