Два письма с постановкой задачи (17.01.00): Еще один комментарий (10.03.00):Малик Максютов:
Еще один комментарий (22.04.00):В.Деров:
Еще один комментарий (27.05.00):
Малик Максютов:
Два ответа-комментария (17.01.00):
Два письма с постановкой задачи:
Стоит задача: выжать максимальную производительность "молотилки": т.е. чисто расчетной программы (консольное приложение без графики и меню). Язык — Fortran. Замена компилятора и/или системы не должна приводить к кардинальным изменениям исходного кода.
Исходные данные:
"Варьируемые" параметры:
Предположения:
Есть рекламная информация от Intel, что их разработка — Fortran-компилятор — полностью использует особенности Intel-процессоров, включая многопроцессорные системы. Однако совершенно нет данных по сопоставлению производительности программ от разных компиляторов.
В рамках MS Windows (95 и NT) преимущество, конечно, за Win95. Выигрыш по нашим тестам где-то 7-8%. И это естественно.
Вопрос: что можно сказать про UNIX и UNIX-подобные системы? Есть ощущение, что там "молотить" должно лучше. Правда, при этом возникает проблема с выбором компилятора в силу шароварности UNIX-продукции.
Кратко суть проблемы: необходимо достигнуть существенного ускорения исполнения чисто расчетной Fortran-программы за счет выбора компилятора/ операционной системы/ специализированных процессоров.
Мы, сотрудники лаборатории "Электромагнитных полей и систем" Московского Энергетического института, с 1974 г. занимаемся расчетом и проектированием электромагнитных устройств различного назначения, используя авторский комплекс программ для анализа трехмерных электромагнитных полей в системах с нелинейными магнитными свойствами ( http://www.mpei.ac.ru/homepages/emag/analis/history.htm).
Требуется найти способ существенного повышения (на порядок или около того) производительности чисто расчетной Fortran-программы (без интерфейса, консольное приложение) за счет выбора специализированного ПО и/или оборудования, оставаясь в масштабах затрат, характерных для PC, а не для рабочих станций.
Алгоритм программы "вылизан" с точки зрения "однопотокового" (последовательного) метода расчета. Но по своей природе "просится" на распараллеливание. Общая структура программы следующая:
В ходе обмена информацией по интересующему нас вопросу могли бы предложить отлаженные тексты используемых нами некоторых Fortran-подпрограмм, являющихся добросовестным копированием весьма качественных алгоритмов из известной в свое время книги: Форсайт Дж., Малькольм М., Моулер К. "Машинные методы математических вычислений", 1980 г.
А именно:
А также расчеты некоторых спецфункций на основе аппроксимаций из справочника Абрамовиц, Стиган.
С уважением, Кулаев Ю.В., Рябинин С.Б.
В ответ на письмо я сразу написал, что "решающее ускорение программы достигается не за счет смены компиляторов и компьютеров, а за счет структурной перестройки программы и алгоритма. Но тут нужно говорить более предметно и конкретно." Мой личный опыт говорит о том, что после тщательного "вылизывания" можно повысить производительность первого варианта своей программы в 1,5-3 раза. Что же касается чужих программ, то тут эффект может быть до 10 раз (за счет "свежего" взгляда).Наиболее же радикальное повышение производительности достигается не за счет "вылизывания", а в результате поиска новых алгоритмических решений.
Но это — общетеоритеческие рассуждения. Поэтому в поиске более практического ответа я обратился за консультацией к своему товарищу-коллеге Сергею Позднякову, который (в отличие от меня) продолжает активно заниматься проблемами математического моделирования. В целом, я могу только присоединиться к высказанным в его письме соображениям.
Ответ 2. (Сергей Поздняков. В форме письма-ответа Андрею Колесову):
Я, наконец, собрался написать реплику на то письмо о распараллеливании. Честно говоря, оно меня слегка смутило — на мой взгляд я не могу предложить ничего конструктивного. Кроме как сказать, что я с большим сомнением отношусь к идее распараллеливания в данном случае. Ниже объясню почему.
Предварительное замечание. Не имея базового высшего физического образования [А.К.: Сергей явно скромничает. Он — доктор геолого-минералогических наук, почти 20 лет занимается математическим моделированием], я не вполне представляю, какими уравнениями описываются трехмерные электромагнитные поля в системах с нелинейными магнитными свойствами (уравнения Максвелла что ли?).
Тем не менее, буду полагать, что это все же нелинейное (коэффициенты уравнений зависят от искомых функций) дифференциальное уравнение в частных производных невысокого порядка. Скажем первый порядок по времени и второй — по пространству. И это уравнение локально (т.е. в нем нет каких-либо интегральных операторов по пространству), поэтому для него можно написать вполне локальную разностную схему, не требующую в каждом уравнении для расчетного узла описывать связи с далекими узлами. Матрица таких уравнений очень слабо заполнена. В общем, как в книжках Самарского.
Кроме того, будем надеяться, что нелинейность достаточно слабая и нашим авторам не придется сталкиваться с действительно трансвычислительными проблемами, возникающими, например, при попытках строго исследовать турбулентность в микромасштабных рамках на модели Навье-Стокса. Кроме того, положим, что при изменении параметров не возникают всякие критические режимы (неустойчивость), когда система почти скачкообразно переходит из одного состояния в другое.
Так вот, если у уважаемых авторов ситуация не выходит за намеченные здесь критические рамки, то я не вижу особых проблем, так как N 5000-10000 — это малое число. Я так понимаю, что под этим N авторы имеют в виду число расчетных узлов в пространстве при интегрировании системы кончено-разностных уравнений. Ты знаешь, что для наших задач геофильтрации я и многие коллеги используем сетки на порядок больше — около 100000 узлов на ПК. Возникающие проблемы при этом связаны в первую очередь с дисковым пространством: при многовариантном счете, когда надо сохранять результаты, считать новые варианты и т.д. и т.п., сотни мегабайт диска заполняются за день-два работы.
Ну и естественно, ты помнишь, с подготовкой полей исходных данных — общая проблема наук о Земле — неоднородность параметров. Вообще в гидрогеодинамике многие полагают, что "большая задача" — это задача, имеющая свыше нескольких миллионов блоков. Для нее нужны мощные станции или суперкомпьютеры.
Я думаю, что авторам следует подумать об улучшении алгоритма решения задачи, а не о распараллеливании. В частности, не знаю, что за алгоритм они используют для итерационного решения системы уравнений. Уж не Гаусса-Зейделя или верхней релаксации? С них мы начинали в 80-е годы. Ты конечно помнишь, что эти методы чувствительны к размеру системы и с ее увеличением падает скорость сходимости. Сейчас у нас, например в гидрогеодинамике, очень популярен метод сопряженных градиентов, который проявляет себя гораздо лучше на больших задачах, чем метод верхней релаксации. Может, им здесь поискать улучшение эффективности счета?
В общем я полагаю, что они должны ответить сами себе на следующие вопросы:
а) Действительно ли им надо повышать именно быстродействие для решения своих научных задач? Ты же знаешь, что для действительно больших сеток на первый план часто выходят проблемы визуализации и анализа результатов. Грубо говоря, лучше я подожду лишнее время, пока идет расчет, но я не смогу ничего понять в результатах, если не "поверчу" рассчитанные поля в разных проекциях, не посчитаю по ним некие интегральные характеристики и т.д.
б) Если все же быстродействие очень важно, не попробовать ли поискать более эффективные методы и алгоритмы решения.
в) Если они все же сядут за распараллеливание, какой выигрыш они ожидают? Грубо говоря, в разряд относительно дешевых компьютеров через год придет машина, позволяющая просчитать их задачу в 5 раз быстрее, чем сегодня. Может, этот год посвятить чему-нибудь полезному и заработать денег на новый компьютер?
Андрей, ты прекрасно понимаешь, что последнее утверждение работает только в случае рационального подхода к делу. Понятно, что если кому-то очень интересно разобраться с проблемой распараллеливания, что-то написать и увидеть, что это действительно работает — скорее всего, он не будет думать о рациональном. Учитывая, что уважаемые коллеги работают в научном секторе (природная любознательность выше средней), то не удивлюсь, что они займутся скалярным распараллеливанием, потом поисками суперкомьютера для проверки возможностей распараллеливания и т.д.
Тут мало что можно сделать.
Прочитал письма и ответы по теме "Повышение производительности FORTRAN программ. Написано много, особенно про "интегрирование системы конечно-разностных уравнений" (сильный удар по МКР!) интересно также выглядит определение "нелинейных дифф. ур-ний". Ничего в математическом смысле я комментировать не стану, а скажу кое-что в более популярном стиле.
Как повысить производительность FORTRAN программы?
Компилятор должен поддерживать коды Вашего процессора. На сегодня, "наш" процессор- Pentium II. Ни один из компиляторов рассмотренных в переписке не поддерживает кодов PII, за исключение Intel Fortran77. Не надо забывать, что PII позволяет оперировать 80-битными данными.
ПОЗВОЛЬТЕ ОТРЕКОМЕНДОВАТЬ:
PC Система PII/PIII - желательно 2 и более CPU. OS - Windows NT/2000 Компилятор Compaq Visual Fortran95 v6.1 (PII support)
Да, самое главное ОБЯЗАТЕЛЬНО нужен Visual KAP v3.6 (кто может "подсказать" ключик к этой программе, буду премного благодарен).
Всем желаю успеха.
Малик С. Максютов mmax@glasnet.ru
P.S. Для чего нужен поток данных более 2GB?? Для удачного своппинга на диск в случае прямых методов решения СЛАУ!
A)
Правда развертка циклов ест память (мой опыт с 2MB-> 48MB). Более подробно об оптимицации кода при помощи компилятора см. http://www.digital.com/ , также надо учесть что опции компилятора надо подбирать для конкретной конфигурации своей машины (размер кэша, оперативной памяти и т.д.) поскольку, я пробовал откомпилировать (чужие программы + чужие опции компилятора ) на своей машине но получал проигрыш в производительности в 1.5 раза по сравнению с скоростью выполнения чужого .....EXE файла на своей же машине.
Но несмотря на все это, окончательный выигрыш который я получил составил порядка 5 раз по скорости исполнения, решаемая задача была следующая: множественные Фурье преобразования + свертка матриц.
Что касается переносимости, то исходники blas библиотеки http://www.netlib.org или ftp://ftp.chg.ru
B) Использовать Matlab для решения итеративных систем СЛАУ
C) Использовать пакет slap (исходники см. http://www.netlib.org или ftp://ftp.chg.ru, библиотеки slap или slatec ) для решения разреженых СЛАУ + blas, возможно это сэкономит память.
Деров А. МИФИ.
Прочитал письмо г. А. Дерова по поводу использования математических библиотек. Хотелось бы еще добавить к сказанному несколько слов.
Действительно, такие библиотеки как BLAS это "промышленный" стандарт в прикладной математике, в частности модули для решения СЛАУ с разреженными матрицами (только итерационные процедуры). Есть еще и пакеты LAPACK и LINPACK. ПОЛНЫЙ пакет BLAS+LINPACK+LAPACK содержится в поставке компилятора Compaq Visual Fortran 6.1. Вместе с дополнениями от ex-Digital он называется Compaq Extended Mathematical Libraries (CXML).
Если речь заходит об использовании итерационных методов решения СЛАУ с использованием пакета BLAS, то не лишним будет немного "покопаться" в "железе" вашего PC. Рекомендую использовать UWSCSI диск как для своппинга так и для записи блоков матрицы. Производительность, за счет разгрузки СПУ на операциях ввода/вывода в этом случае значительно возрастает (в несколько раз!). Конечно, это справедливо лишь при условии, что вы располагаете только EIDE устройствами, пусть даже UDMA.
Неплохим выбором для библиотеки может стать и IMSL также поставляемая с компилятором Compaq Visual Fortran 6.1. На мой взгляд , наиболее интересны библиотеки, в которых содержатся ПРЯМЫЕ методы решения разреженных систем (в наше время дефицит оперативной памяти уже не так актуален как 3-5 лет назад!)