хранение в памяти больших матриц

[venco]

y_nikolaenko в сообщении #355866 писал(а):

gris,

не обижайтесь: здесь не место для лекций, а современные технологии перемножения матриц довольно сложны.

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

[gris]

Про шею Вы сами сказали. Речь шла не о современных многопоточных технологиях, а о ЭВМ эпохи 60-тых годов прошлого тысячелетия. С матрицей на перфоленте.

[EugenePhoenix]

y_nikolaenko писал(а):

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

Может литературу хорошую подскажите?

[y_nikolaenko]

gris в сообщении #355871 писал(а):

Про шею Вы сами сказали. Речь шла не о современных многопоточных технологиях, а о ЭВМ эпохи 60-тых годов прошлого тысячелетия. С матрицей на перфоленте.

Где я говорил: "всех в шею"? И многопоточные технологии не имеют никакого отношения к алгоритму перемножения матриц.

-- Пт сен 24, 2010 21:15:43 --

EugenePhoenix в сообщении #355879 писал(а):

y_nikolaenko писал(а):

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

Может литературу хорошую подскажите?

Возьмите IDA Pro и раздраконьте алгоритм перемножения из высокооптимизированного пакета: лучше литературы не найдете. Я действовал именно так.

[Zealint]

gris в сообщении #355830 писал(а):

Zealint, битовое поле из белого шума при сжатии стандартным алгоритмом пожалуй ещё увеличится в размерах.

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

Кстати, ещё вариант: существуют довольно быстрые жёсткие диски. А вообще, все зависит от того, что мы хотим с этой матрицей делать. Для стандартных операций над такими матрицами, например, сейчас популярно использовать распределённые вычисления, когда вся матрица умещается в нескольких компьютерных классах университета / лаборатории.

[worm2]

Кажется, я понял, что имел в виду y_nikolaenko.
Даже если матрица хранится по строкам, всё равно можно умножить её справа на вектор (а вектор будет, соответственно, слева) за один проход ленты, не затрачивая дополнительной памяти (в памяти хранится только умножаемый вектор, накапливаемый вектор-результат и текущая загруженная с ленты строка матрицы).

[gris]

Себя не процитируешь, так и не заметят.

gris в сообщении #355817 писал(а):

Конечно, имея в памяти место для вектора, для одной строки матрицы и для строки результата можно организовать умножение в один проход с каким угодно способом "подачи" матрицы в память. Хотя время может существенно вырасти при отходе от последовательных процессов (в памяти, даже не на ленте).Но вот бывало что место есть только для вектора и для части строки или столбца. Вот тут и приходилось держать два рулона на каждую матрицу

[worm2]

Цитата:

Себя не процитируешь, так и не заметят.

Блин, несколько секунд не хватило, чтобы ещё раз перечитать то сообщение и удалить своё.
Придётся теперь оставлять на память свидетельство позора

[y_nikolaenko]

EugenePhoenix,

Когда наберетесь знаний и опыта, то можно приступать и к следующему этапу, а именно к самостоятельной работе, как здесь:
post353628.html#p353628
Но это не для всех, во всяком случае, не для меня: я там разбирался в нескольких десятках строчек исходного кода неделю.

[Vassil]

Возвращаясь к шестидесятым-семидесятым прошлого века, могу свидетельствовать, что была задача при которой:
- матрица на матнитной ленте (по строкам) много раз и всегда только слева умножала вектор-столбец (в памяти);
- на двух разных лентопротяжках были две копия одной и той же матрицы, чтобы экономить на так называемом времени обратной перемотки ленты (REWIND). Пока одно копие перематывалось, на втором копие, с его начала и дальше, без ожидания проводилось очередное умножение.

[gris]

Vassil, за такой алгоритм y_nikolaenko не то что в шею, а наверное вообще бы расстрелял и повесил.
А вот если бы ту матрицу переписать по столбцам, то и перематывать не пришлось бы.

(Оффтоп)

Вот вопрос - почему ни слова? Для кого стараюсь...
А вообще я всё придумал. Не было спички М20.

[Circiter]

2EugenePhoenix

Цитата:

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

Ну, в таком случае, т.е. при хранении в памяти лишь части матрицы, неизбежно использование жесткого диска и техник кэширования. Технические приемы, упомянутые некоторыми участниками обсуждения (gris и Vassil), вроде хранения различных реплик данных в различных форматах, конечно же должны исследоваться и применяться. Жесткие диски действительно являются довольно медлительными устройствами и рациональное их использование, в том числе и оптимизация позиционирования головки, стоит дополнительных, но, безусловно, оправданных затрат и возможных неудобств. Да и дублирование информации в распределенных системах ещё никому не вредило. :)

Но я, конечно, хотел сказать совсем другое. Лично мне не приходилось иметь дело с большими матрицами, допускающими применение эффективных схем хранения за счет наличия у них какой-либо структуры, будь-то блочность, разряженность, энтропийная избыточность (сжимаемость) или ещё что... Разве что писал простой встраиваемые поисковый движок, основанный на векторной модели документов; но там своя специфика, все совсем по-другому...

Зато писалась небольшая библиотека для работы с большими терапиксельными картинками (астрономическими, в основном). Хотелось очень большое изображение, заведомо не помещающееся в ОЗУ, просматривать на дешевом железе не испытывая при этом каких-либо неудобств. То есть, библиотека должна была в первую очередь позволять плавно прокручивать изображение при произвольном масштабе.

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

К слову сказать, разработка была заморожена, особенно после ознакомления с софтинами наподобие vips/graphicsmagick/imagemagick/&c. :) Ну да ладно... Я вот думаю, что возможно в решении ваших задач могут помочь аналогии именно с обработкой изображений.

Как раз-таки здесь, как мне кажется, важна именно "неодномерность" информации в матрице, то есть, локальность обрабатывающих алгоритмов и последовательность доступа. Например, возится ваш алгоритм с некоторым куском матрицы (e.g., с квадратом фиксированных размеров, скажем $10000\times 10000$), можно ведь за это время подгрузить (в фоне) с диска в память соседние куски (4 или даже 8 штук). Если алгоритм с большой вероятностью перейдет в один из соседних кусков, то тот будет уже в памяти и это не повлияет на производительность (понятно, что кусками могут быть и полосы из нескольких строк; отношения соседства тоже могут быть различными). Примерно так...

Можно ещё использовать компромиссные решения, например пользуясь файлами, отображаемыми в память (то есть, позволяя часть работы по оптимальному кэшированию/своппингу выполнять операционной системе); это, как правило, приводит к заметному ускорению по сравнению с самостоятельным использованием дисковых/файловых IO-операций.

Вот такие вот мыслишки... Может быть не в тему, но все же...

[y_nikolaenko]

a cache-oblivious algorithm: http://en.wikipedia.org/wiki/Cache-oblivious_algorithm
Примеры из Intel Cilk++ включены в Parallel Studio 2011.

[vitaly333]

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

[EugenePhoenix]

Цитата:

а что вы собираетесь делать с этими матрицами?

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