2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 linpack
Сообщение02.08.2007, 13:18 


17/09/05
121
Уважаемые эксперты!

Есть пакет linpack (http://www.netlib.org/linpack/) для тестирования суперкомпьютеров.
А кто-нибудь что-нибудь может сказать о его вычислительных свойствах?
Нет ли в нём каких-то больших ошибок и т.п.?

Заранее спасибо.

 Профиль  
                  
 
 Re: linpack
Сообщение02.08.2007, 16:32 
Заслуженный участник


15/05/05
3445
USA
nworm писал(а):
Есть пакет linpack ... для тестирования суперкомпьютеров.
... Нет ли в нём каких-то больших ошибок и т.п.?
1. Это не пакет для тестирования, а пакет для практического использования. Другое дело, что он использовался и для тестирования производительности суперкомпьютеров.
2. Linpack разработан ок. 30 лет назад. С тех пор он активно применялся.
3. Лучше перейти на разработанный лет 15 назад Lapack, который включает и функциональность Eispack..
4. Я эти пакеты использовал в течение многих лет (НЕ на суперкомпьютерах) и с проблемами не сталкивался.
5. Думаю, что вероятность ошибок близка к 0.
6. Требуется грамотный выбор алгоритмов. Например, не следует использовать разложение Холецкого для несимметричных матриц.

 Профиль  
                  
 
 
Сообщение02.08.2007, 23:12 


17/09/05
121
Спасибо.

 Профиль  
                  
 
 
Сообщение13.08.2007, 22:35 


17/09/05
121
Вот нашёл в linpack-овской программе zhifa.f (factors a complex Hermitian matrix, by elimination with symmetric pivoting)

Код:
c        info    integer
c                = 0  normal value.
c                = k  if the k-th pivot block is singular. this is
c                     not an error condition for this subroutine,
c                     but it does indicate that zhisl or zhidi may
c                     divide by zero if called.


Что-то я никак не могу понять какой они там численный метод используют и, следовательно, что это за ошибка. :oops:

 Профиль  
                  
 
 
Сообщение15.08.2007, 18:29 
Заслуженный участник


15/05/05
3445
USA
Тут же написано: "the k-th pivot block is singular".
Это примерно соответствует случаю, когда для действительных симметричных матриц на очередном шаге k все элементы столбца k, начиная с a(k,k) и ниже, равны 0.

Поправка: не "ниже a(k,k)", а "начиная с a(k,k) и ниже"

 Профиль  
                  
 
 Re: linpack
Сообщение26.08.2007, 13:38 


05/08/07

194
Yuri Gendelman писал:
4. Я эти пакеты использовал в течение многих лет (НЕ на суперкомпьютерах) и с проблемами не сталкивался.
5. Думаю, что вероятность ошибок близка к 0.


Необходимо быть осторожным с RRR (Relatively Robust Representations algorithms).
Только в версии LAPACK 3.1 он стал более-менее приемлемым (В этой версии глюки, отмеченные на моей странице http://www.thesa-store.com/products (для процессора P4), уже не проявляются, но "выползают" более тонкие ошибки).

 Профиль  
                  
 
 Re: linpack
Сообщение26.08.2007, 14:52 
Заслуженный участник


15/05/05
3445
USA
abc_qmost писал(а):
Необходимо быть осторожным с RRR (Relatively Robust Representations algorithms). Только в версии LAPACK 3.1 он стал более-менее приемлемым
Большое спасибо за информацию. Я с этим алгоритмом не был знаком. Как я понял, он появился в середине 90-х, т.е. для меня - "после того как". Постараюсь найти статьи I. S. Dhillon and B. N. Parlett.

 Профиль  
                  
 
 
Сообщение26.08.2007, 15:00 


30/10/06
33
Уважаемый abc_qmost!

Судя по содержанию вашей интернет-страницы, вы - тот самый человек, которой сможет компетентно может ответить на три моих давно назревших вопроса:

1) Сильно ли ушли вперед АЛГОРИТМИЧЕСКИ процедуры нахождения всех собственных значений и векторов действительной симметричной матрицы малых порядков по сравнению со временами создания Справочника? Например, матрица с габаритами типа 64х64, по-видимому, не требующая никаких дополнительных операций для деления ее на блоки. Во сколько раз можно надеяться ускорить ее обработку по сравнению со старым алгоритмом из EISPACK (tred2+tql2)? Подчеркиваю, что вопрос касается именно алгоритмической сложности алгоритма (число умножений, делений, выборки), а отнюдь не реализаций алгоритма со всевозможными ухищрениями на разных Core Duo и им подобным.

2) По своему опыту знаю, насколько быстрее начинает работать алгоритм после замены С-ишной процедуры вычисления скалярного произведения на ассеблерную. Главную роль тут, конечно же, играет возможность использовать внутренний регистр процессора в качестве накопителя суммы, в то время как компилятор Си заставил бы на каждом обороте цикла дважды лазить в память, считывая и записывая текущее значение суммы. В связи с этим, у меня к вам вопрос, как к практику: во сколько раз быстрее удается организовать вычисления скалярного произведения двух массивов типа double при переходе на SSE2 и SSE3 инструкции? Нет ли у вас статистики такого рода? Конкретно меня интересует сравнение 3-х типов вычислений: а) накопление суммы в регистре FPP87, b) использование SSE2 и SSE3 (не помню сейчас, что появилось в SSE3 нового), и, наконец, c) SSE4 (где вроде бы появилась новая инструкция DPPD — Dot Product of Packed Double Precision Floating-Point Values).

3) И последний вопрос на эту тему. Известно, что суммирование больших и малых величин (а накопление скалярного произведения - как раз такой случай) является одной главных источников возникновения погрешностей. При вычислениях на FPP87 сумма может накапливается в его регистре, имеющим более длинную мантиссу, чем double (так называемый "long double" или TBYTE). Это позволяло в большинстве случаев иметь верным даже последний знак суммы после записи ее в double-элемент матрицы. А с переходом на SSE тип long double стали всячески избегать, исключив его даже из компиляторов (например, MS Studio 2005). Причина тут ясна - некратность длины этого типа степени числа 2, что не обеспечивает выравнивания. Однако как оцениваете именно вы такое обрезание мантиссы? Существенна ли эта потеря в деле матричных вычислений? Каково ваше мнение на этот счет?

 Профиль  
                  
 
 Re: linpack
Сообщение26.08.2007, 15:44 
Заслуженный участник


15/05/05
3445
USA
abc_qmost писал(а):
Необходимо быть осторожным с RRR (Relatively Robust Representations algorithms). Только в версии LAPACK 3.1 он стал более-менее приемлемым
Пока искал статьи Диллона по RRR, наткнулся на другую его статью: "Current Inverse Iteration Software Can Fail", by Inderjit S. Dhillon, BIT Numerical Mathematics, 38(4), p.685-704 (1998). Цитата из аннотации к ней: "...as we show in this paper, the implementations in EISPACK and LAPACK may fail...".
Т.е. в этих пакетах вероятность ошибки все-таки больше нуля :). Хотя IMHO в наиболее популярных методах, типа разложения Холецкого или QR, все многократно проверено.

 Профиль  
                  
 
 
Сообщение26.08.2007, 16:31 


05/08/07

194
Oam писал(а):
Уважаемый abc_qmost!

Судя по содержанию вашей интернет-страницы, вы - тот самый человек, которой сможет компетентно может ответить на три моих давно назревших вопроса:

1) Сильно ли ушли вперед АЛГОРИТМИЧЕСКИ процедуры нахождения всех собственных значений и векторов действительной симметричной матрицы малых порядков по сравнению со временами создания Справочника? Например, матрица с габаритами типа 64х64, по-видимому, не требующая никаких дополнительных операций для деления ее на блоки. Во сколько раз можно надеяться ускорить ее обработку по сравнению со старым алгоритмом из EISPACK (tred2+tql2)? Подчеркиваю, что вопрос касается именно алгоритмической сложности алгоритма (число умножений, делений, выборки), а отнюдь не реализаций алгоритма со всевозможными ухищрениями на разных Core Duo и им подобным.

2) По своему опыту знаю, насколько быстрее начинает работать алгоритм после замены С-ишной процедуры вычисления скалярного произведения на ассеблерную. Главную роль тут, конечно же, играет возможность использовать внутренний регистр процессора в качестве накопителя суммы, в то время как компилятор Си заставил бы на каждом обороте цикла дважды лазить в память, считывая и записывая текущее значение суммы. В связи с этим, у меня к вам вопрос, как к практику: во сколько раз быстрее удается организовать вычисления скалярного произведения двух массивов типа double при переходе на SSE2 и SSE3 инструкции? Нет ли у вас статистики такого рода? Конкретно меня интересует сравнение 3-х типов вычислений: а) накопление суммы в регистре FPP87, b) использование SSE2 и SSE3 (не помню сейчас, что появилось в SSE3 нового), и, наконец, c) SSE4 (где вроде бы появилась новая инструкция DPPD — Dot Product of Packed Double Precision Floating-Point Values).

3) И последний вопрос на эту тему. Известно, что суммирование больших и малых величин (а накопление скалярного произведения - как раз такой случай) является одной главных источников возникновения погрешностей. При вычислениях на FPP87 сумма может накапливается в его регистре, имеющим более длинную мантиссу, чем double (так называемый "long double" или TBYTE). Это позволяло в большинстве случаев иметь верным даже последний знак суммы после записи ее в double-элемент матрицы. А с переходом на SSE тип long double стали всячески избегать, исключив его даже из компиляторов (например, MS Studio 2005). Причина тут ясна - некратность длины этого типа степени числа 2, что не обеспечивает выравнивания. Однако как оцениваете именно вы такое обрезание мантиссы? Существенна ли эта потеря в деле матричных вычислений? Каково ваше мнение на этот счет?

Ответ на 1 вопрос:
Если оставить в стороне блочные методы, которые не имеет смысла применять для малых матриц, то сильно изменилась tql2, вернее та ее часть, которая отвечает за работу с трехдиагональной матрицей (и то недавно). Скорость этой части в некоторых случаях возрасла на 500%. Этот алгоритм реализован в пакете Intel MKL.
Ответ на 2 вопрос:
Я специально таких замеров не делал. С точки зрения SS2 меня интересовали BLAS LEVEL 2 для трехдиагонализации (умножение м-цы на вектор - увеличение скорости ~ в 2.5 раза) и BLAS LEVEL 3 (перемножение м-ц - увеличение скорости ~ в 8 раз). Но алгоритмы очень хитрые и не сводятся к простой реализации скалярного произведения.
Что касается SSE4, то ничего не могу сказать.
Ответ на 3 вопрос:
"long double" есть в Intel'овском C-ном трансляторе. Под него выделяется 16 байт.
Что касается полезности "long double", то он позволяет решать более сложные задачи, чем отмечено в Вашем 3-ем пункте.
Что касается MS Studio 2005, то для технологии NET "long double" как кость в горле.

 Профиль  
                  
 
 
Сообщение26.08.2007, 17:48 


30/10/06
33
abc_qmost писал(а):
Если оставить в стороне блочные методы, которые не имеет смысла применять для малых матриц, то сильно изменилась tql2, вернее та ее часть, которая отвечает за работу с трехдиагональной матрицей (и то недавно). Скорость этой части в некоторых случаях возрасла на 500%. Этот алгоритм реализован в пакете Intel MKL.

К моему большому сожалению, пакет Intel MKL, для меня недоступен.Впрочем, даже в ином случае я был бы бессилен вытащить алгоритм этой функции из скомпилированной библиотеки.
Поскольку, как вы пишите, увовершенствования процедры произошли недавно, то скорее всего они не описаны в той книге, которую вы рекомендоваои мне для чтения. В связи с этим, не были бы вы так любезны привести хотя бы ссылку (в интернете) на алгоритм такого рода?(лучше код, чем пространное описание).Или хотя бы назовите, под каким именем такая процедура известна. Тогда бы у меня появился хотя бы шанс с ней ознакомиться.

abc_qmost писал(а):
"long double" есть в Intel'овском C-ном трансляторе. Под него выделяется 16 байт.
Что касается полезности "long double", то он позволяет решать более сложные задачи, чем отмечено в Вашем 3-ем пункте.
Что касается MS Studio 2005, то для технологии NET "long double" как кость в горле..

Сказанное вами мне хорошо известно. Мой же вопрос касался того, как вы поступаете в этой непростой ситуации? "Смирились", по команде отказавшись от типа long double, или, несмотря ни на что, продолжаете его применять в ваших алгоритмах? Причем даже вопреки тому, что SSE- инструкции этот тип не поддерживают.

 Профиль  
                  
 
 
Сообщение26.08.2007, 19:20 


05/08/07

194
Oam писал(а):
К моему большому сожалению, пакет Intel MKL, для меня недоступен.Впрочем, даже в ином случае я был бы бессилен вытащить алгоритм этой функции из скомпилированной библиотеки.
Поскольку, как вы пишите, увовершенствования процедры произошли недавно, то скорее всего они не описаны в той книге, которую вы рекомендоваои мне для чтения. В связи с этим, не были бы вы так любезны привести хотя бы ссылку (в интернете) на алгоритм такого рода?(лучше код, чем пространное описание).Или хотя бы назовите, под каким именем такая процедура известна. Тогда бы у меня появился хотя бы шанс с ней ознакомиться

Я не знаю, где описан этот алгоритм. Подозреваю, что за его основу взята диссертация главного менеджера Intel MKL. У меня есть ссылка на эту диссертацию. Найду - вышлю. (Пришлите свой адрес. Мой email найдете на моей странице).
Oam писал(а):
Сказанное вами мне хорошо известно. Мой же вопрос касался того, как вы поступаете в этой непростой ситуации? "Смирились", по команде отказавшись от типа long double, или, несмотря ни на что, продолжаете его применять в ваших алгоритмах? Причем даже вопреки тому, что SSE- инструкции этот тип не поддерживают.

Какой смысл применять "long double", если я уже на первом шаге (трехдиагонализации) использую SSE?

 Профиль  
                  
 
 Re: linpack
Сообщение27.08.2007, 13:27 


05/08/07

194
Yuri Gendelman писал(а):
abc_qmost писал(а):
Необходимо быть осторожным с RRR (Relatively Robust Representations algorithms). Только в версии LAPACK 3.1 он стал более-менее приемлемым
Пока искал статьи Диллона по RRR, наткнулся на другую его статью: "Current Inverse Iteration Software Can Fail", by Inderjit S. Dhillon, BIT Numerical Mathematics, 38(4), p.685-704 (1998). Цитата из аннотации к ней: "...as we show in this paper, the implementations in EISPACK and LAPACK may fail...".
Т.е. в этих пакетах вероятность ошибки все-таки больше нуля :). Хотя IMHO в наиболее популярных методах, типа разложения Холецкого или QR, все многократно проверено.

Алгоритм для алгебраической проблемы с.з. и с..в. симметричной трехдиагональной м-цы в последних версиях Intel MKL изменен.

 Профиль  
                  
 
 Re: linpack
Сообщение27.08.2007, 14:07 
Заслуженный участник


15/05/05
3445
USA
abc_qmost писал(а):
Алгоритм для алгебраической проблемы с.з. и с..в. симметричной трехдиагональной м-цы в последних версиях Intel MKL изменен.
А что именно изменено, математика или реализация? Если математика, то нет ли у Вас ссылок на детали?

 Профиль  
                  
 
 Re: linpack
Сообщение27.08.2007, 16:11 


05/08/07

194
Yuri Gendelman писал(а):
abc_qmost писал(а):
Алгоритм для алгебраической проблемы с.з. и с..в. симметричной трехдиагональной м-цы в последних версиях Intel MKL изменен.
А что именно изменено, математика или реализация? Если математика, то нет ли у Вас ссылок на детали?

В некоторых случаях скорость возрасла в 5 раз. Думаю, что изменена математика. Надо смотреть диссертацию менеджера (кажется, он главный в Intel MKL, т.к., когда я с ними переписывался, командова он). Напишите мне по адресу с моей страницы, я Вам вышлю координаты.

Добавлено спустя 1 час 26 минут 20 секунд:

Yuri Gendelman писал(а):
abc_qmost писал(а):
Алгоритм для алгебраической проблемы с.з. и с..в. симметричной трехдиагональной м-цы в последних версиях Intel MKL изменен.
А что именно изменено, математика или реализация? Если математика, то нет ли у Вас ссылок на детали?


Нашел письмо от Greg'а:
...
To get it, grab http://www.cs.utk.edu/~ghenry/thesis.ps

Look at Chapter 4.2. I talk about using lookahead shifts to accelerate the QR algorithm. I spend way too much
time buying a small amount of performance in the unsymmetric case, and then as an afterthought, I discuss what I call a
standard lookahead shift for the symmetric case in 4.2.8. For all but very small matrices, the lookahead approach I
suggest is ideal.

There is no claim that this is in any way related to anything else. The only claim is that MKL 7.2 does not yet
currently use this technology and may in the future contain these useful techniques.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу 1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group