Как программисты работают с большими массивами? , Решение СЛАУ, не помещающихся в оперативной памяти

До сих пор я работал со СЛАУ сравнительно небольших размерностей. Матрицы таких СЛАУ можно было размещать в оперативной памяти.
Матрицы плотно заполнены.
Вообще говоря я пока еще не знакомился с теорией, относящейся к данному вопросу, поскольку, как я уже писал, не было такой необходимости, а в университете я этого не проходил.
Пока у меня есть только два решения.
Первое - записывать получаемые массивы в файл, то есть размещать их на жестком диске, и запаршивать каждый элемент когда это необходимо. Тогда это может очень увеличить время счета.
Второе - вообще не считать коэффициенты матрицы до тех пор, пока соответствующий элемент не затребуется на определнном шаге алгоритма, решающего СЛАУ, и считать его только в этот момент. Тогда придется один и тот же элемент определять несколько раз, да и время счета, по-моему, не сильно будет отличаться от первого варианта (или я ошибаюсь?).
В общем, вопрос задан в названии темы. Прошу поделиться опытом.

Telc, а какая это размерность, что в оперативку не влазит?

Так, если даже 10000 уравнений, то 10^10 размерность... Вроде так-то немного, а вот "проклятие размерности".
В файл сохранять - это не выход, по-моему. Благо виртуальная память на то и придумано, чтоб файл подкачки раздувать. Ставьте 64-битную операционку, жёсткий диск побольше и должно влазить в нёё-то.

Порядка 50000 уравнений (матрица квадратная, плотно заполненная).

Круто. С наскока могу лишь предолжить опять 64-битную систему для решения сей проблемы, хотя наверняка есть более оптимальные способы.

В windows создаётся страница памяти нужного размера и в ней храните свой мегамассив. ОС самостоятельно будет принимать решение о выгрузке/загрузке страницы

Цитата AndreyK @ 05.11.07, 19:56

В windows создаётся страница памяти нужного размера и в ней храните свой мегамассив. ОС самостоятельно будет принимать решение о выгрузке/загрузке страницы

А как это сделать? Этот вариант является наиболее оптимальным?

Сообщение отредактировано: Telc - 05.11.07, 20:39

AndreyK
И где это вы такую глупость вычитали?


Telc
Массив на диск. Доступ по средство чатения. В память должно считываться только необходимые данные. Алгоритм обработки должен снизить число обращений к диску.

Решил полной ответ написать.
Для доступа к файлу есть несколько механизмов. Просто читать файл по частям в память или целеком.

Можно отоброзить файл в память. Тогда можно будет работать с файлом как с памятью. Если у вас физической памяти меньше чем файл. То виндос будет выгружать часть данных из памяти а нужную подгружать.
Память разбита на страницы, все страницы имеют фиксированнный размер. Так что выгрузка загрузка осуществляется страницами. Если попробовать что-то дописать. То виндоус сам расширит требуемую память.

Теперь о том почему так не сделать.
Во-первых в 32-битных системах есть ограничения на размер отоброжаемого файла.
Ограничение это то что пользовательскому процессу дается 2ГБ виртуальной памяти, в некоторых случаях 3ГБ. Но она разбита на куски. Так что максимальный размер ограничивается размера наибольшего куска.
Так что тут выход 64-битная ОС.

Во-вторых Если физическая память исчерпона, то программа будет просто ужастно тормазить. Загружая/выгружая страницы памяти.

Но практика показывает, что если читать файл вручную, а не отображать в память, то можно получить прирост.

Сообщение отредактировано: Pavia - 05.11.07, 21:15

Цитата Telc @ 05.11.07, 14:37

Порядка 50000 уравнений (матрица квадратная, плотно заполненная).

Лучше всего найти способ обойти необходимость решать такие системы - может, сам метод решения задачи изменить.
Или уж кластер использовать.

Нет, обойти такую проблему принципиально не получится.
Вопрос по сообщению nvm: как использовать?
Вопрос по сообщению Pavia: что будет работать быстрее: записать на диск массив и затем, по мере необходимости считывать тот или иной элемент, или вообще не запоминать массив (ни на диске ни в оперативке), а считать конкретный элемент непосредственно перед его использованием (например, надо умножить a_{i,j} на b_{j} я вызываю процедуру, которая мне посчитает этот элемент a_{i,j} и тогда я перемножу его на b_{j})?

Telc
Если ты будешь считывать из файла один элемент, то это медленно. Лучше так прочитал строчку умножил ее на элимент сохронил. Или считал две строчки произвел между ними операции сохронил результаты.

Насчет вычислений. Все зависит от скорости может посчитать быстрее будет. А может и нет.

Telc
50000x50000x8=18,62 Гб. Тебе нужен хороший многопроцессорный сервер с как минимум 32 Гб оперативки и 64-х разрядная операционка. Если памяти не хватит, то время решения (и так немаленькое) увеличится еще на порядок даже при условии оптимального чтения с диска (то есть все строки уравнения хранятся на диске последовательно и обрабатываются тоже последовательно). Я вообще не понимаю, как ты собираешься решать такую систему, понадобятся очень эффективные алгоритмы (метод Гаусса слишком медленный).

В принципе, если использовать метод Гаусса, то при прямом и обратном обходе вполне можно обрабатывать матрицу кусками, влезающими в оперативку, ведь внутренний цикл работает только с двумя строками одновременно. К тому же это легко распарраллеливается.

Добавлено 06.11.07, 08:11
Предположим, что система решается методом Гаусса => это 2x50000 проходов по матрице, пусть скорость чтения с диска - 120 Мб/сек (рэйд там какой-нибудь). 18.62*1024*2*50000/120/86400=184 дня непрерывной работы. Так что нужно или долго ждать или использовать более эффективный метод...

Сообщение отредактировано: Pacific - 06.11.07, 08:11

Цитата Pacific @ 06.11.07, 07:53

Telc
50000x50000x8=18,62 Гб. Тебе нужен хороший многопроцессорный сервер с как минимум 32 Гб оперативки и 64-х разрядная операционка. Если памяти не хватит, то время решения (и так немаленькое) увеличится еще на порядок даже при условии оптимального чтения с диска (то есть все строки уравнения хранятся на диске последовательно и обрабатываются тоже последовательно). Я вообще не понимаю, как ты собираешься решать такую систему, понадобятся очень эффективные алгоритмы (метод Гаусса слишком медленный).

В принципе, если использовать метод Гаусса, то при прямом и обратном обходе вполне можно обрабатывать матрицу кусками, влезающими в оперативку, ведь внутренний цикл работает только с двумя строками одновременно. К тому же это легко распарраллеливается.

Добавлено 06.11.07, 08:11
Предположим, что система решается методом Гаусса => это 2x50000 проходов по матрице, пусть скорость чтения с диска - 120 Мб/сек (рэйд там какой-нибудь). 18.62*1024*2*50000/120/86400=184 дня непрерывной работы. Так что нужно или долго ждать или использовать более эффективный метод...

Я вот не понимаю, зачем человеку 32 ГБ оперативки. Таких компов днём с огнём не сыскать. Вот, например, взять 32-битную винду. Там можно захапать теоретически 4 ГБ оперативки, но никто же не говорит, что нужно, чтоб все 4 ГБ были вставлены в комп. Этим и занимается виртуальная память, раздувая оперативку до максимально возможного значения за счёт файла подкачки.

Сообщение отредактировано: experimenter - 06.11.07, 08:16

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

Цитата Pacific @ 06.11.07, 08:18

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

Да, теперь понимаю. Ну, тогда давайте предложим человеку купить майнфрейм.