2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 19:56 
y_nikolaenko в сообщении #355866 писал(а):
gris,

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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:07 
y_nikolaenko писал(а):

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


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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:08 
gris в сообщении #355871 писал(а):
Про шею Вы сами сказали. Речь шла не о современных многопоточных технологиях, а о ЭВМ эпохи 60-тых годов прошлого тысячелетия. С матрицей на перфоленте.

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

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

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

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


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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:48 
gris в сообщении #355830 писал(а):
Zealint, битовое поле из белого шума при сжатии стандартным алгоритмом пожалуй ещё увеличится в размерах.

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

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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:54 
Аватара пользователя
Себя не процитируешь, так и не заметят. :-)

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:56 
Аватара пользователя
Цитата:
Себя не процитируешь, так и не заметят. :-)
Блин, несколько секунд не хватило, чтобы ещё раз перечитать то сообщение и удалить своё.
Придётся теперь оставлять на память свидетельство позора :D

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 21:00 
EugenePhoenix,

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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 21:49 
Аватара пользователя
Vassil, за такой алгоритм y_nikolaenko не то что в шею, а наверное вообще бы расстрелял и повесил. :-)
А вот если бы ту матрицу переписать по столбцам, то и перематывать не пришлось бы.

(Оффтоп)

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение02.10.2010, 11:53 
2EugenePhoenix
Цитата:
Если кто знает, подскажите какой-нибудь альтернативный вариант хранеия матриц. Наверно, чтобы в памяти находилась не вся матрица сразу, а только ее часть.

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

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

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

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

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

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

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

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

 
 
 
 Re: хранение в памяти больших матриц
Сообщение02.10.2010, 17:49 
a cache-oblivious algorithm: http://en.wikipedia.org/wiki/Cache-oblivious_algorithm
Примеры из Intel Cilk++ включены в Parallel Studio 2011.

 
 
 
 Re: хранение в памяти больших матриц
Сообщение09.10.2010, 23:03 
EugenePhoenix, а что вы собираетесь делать с этими матрицами? Если матрицы большие и плотные и вы хотите решать перемножать их то тут однозначно нужно использовать блочный подход.

 
 
 
 Re: хранение в памяти больших матриц
Сообщение12.10.2010, 17:21 
Цитата:
а что вы собираетесь делать с этими матрицами?

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

 
 
 [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group