2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 19:56 
Заслуженный участник


04/05/09
4582
y_nikolaenko в сообщении #355866 писал(а):
gris,

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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 19:58 
Заслуженный участник
Аватара пользователя


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

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


05/09/10
10
y_nikolaenko писал(а):

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


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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:08 
Заблокирован


18/09/10

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

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

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

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

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


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

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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:48 


26/01/10
959
gris в сообщении #355830 писал(а):
Zealint, битовое поле из белого шума при сжатии стандартным алгоритмом пожалуй ещё увеличится в размерах.

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

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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:50 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:54 
Заслуженный участник
Аватара пользователя


13/08/08
14429
Себя не процитируешь, так и не заметят. :-)

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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 20:56 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Цитата:
Себя не процитируешь, так и не заметят. :-)
Блин, несколько секунд не хватило, чтобы ещё раз перечитать то сообщение и удалить своё.
Придётся теперь оставлять на память свидетельство позора :D

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


18/09/10

183
EugenePhoenix,

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

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


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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение24.09.2010, 21:49 
Заслуженный участник
Аватара пользователя


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

(Оффтоп)

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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение02.10.2010, 11:53 
Заслуженный участник


26/07/09
1559
Алматы
2EugenePhoenix
Цитата:
Если кто знает, подскажите какой-нибудь альтернативный вариант хранеия матриц. Наверно, чтобы в памяти находилась не вся матрица сразу, а только ее часть.

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

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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение02.10.2010, 17:49 
Заблокирован


18/09/10

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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение09.10.2010, 23:03 


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

 Профиль  
                  
 
 Re: хранение в памяти больших матриц
Сообщение12.10.2010, 17:21 


05/09/10
10
Цитата:
а что вы собираетесь делать с этими матрицами?

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

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

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



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

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


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

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