Я, наверно, понял Вашу идею. Вы предлагаете в task'и передавать исходную матрицу и еще необходимые индиксы для того, чтобы выделять в исходной необходимые подматрицы. Хммм, да, скорее всего при грамотной реализации это даст существенный прирост производительности, но вот читаймость и ясность кода упадет в разы.( Тоже касается и с выделением линейного массива. Думаю, лучше выбор решения оставить за тем, кому оно понадобится. Всё таки приросты производительности будут на очень больших матрицах(На практике почти не встречаются). А для матриц меньше 500*500 лучше оставить код более легкий и краткий код.
Спасибо за Ваш интерес.
P.S. кст, Вы один из тех, из-за кого наш преподаватель отменил занятие(из-за Joker), так что, возможно, если бы не Вы, то этой статьи и не было бы:))
Исправил! Даже стандарный пример взять нельзя:( Всё нужно перепроверять. Фразу с «особенностью» убрал.
В нашем исходном коде всё ок. Валидация проверит корректность размерностей матриц да и не только это.
Из того, что реализация только на Java, не значит, что её нельзя сделать быстрой
А кто сказал, что реализация работает медленно?) Просто есть противоречия в словах. То память расходуется не правильно, то в джавовское управление памятью не замедляет алгоритм. Если есть конкретные идеи, то предлагайте. А то это перерастает в какой-то холивар)
Вы правы. Так действительно будет быстрей, но на итоговую скорость работы всего алгоритма вряд ли повлияет. Зато код станет кратче.
Что касается копирования, да их тут много. Подобные алгоритмы в принципе решаются на других языка, где имеется соответсвующая гибкость работы с памятью. Мы же говорим про реализацию только на Java.
Примечательно, что Fortran не имеет такой проблемы. Многомерные массивы в нем хранятся по столбцам. Поэтому, кеш будет эксплуатироваться как следует и штатная реализация кубического алгоритма будет работать в разы быстрее.
В нашей статье есть ссылка на другую хабра-статью с траспонированием и там сказано, что в Фортране не потребуется делать траспонирование и обычный алгоритм будет работать в разы быстрей и кэшем всё тоже ок.
Спасибо за Ваш интерес!)
P.S. «magic» я упомянул с иронией, не более
Траспонирование — это не какой-то magic. Оно нужно сугубо для Java, это её особенность чтения массивов. На других языках (например: Fortran) вообще не потребуется никого траспонировать.
Предложите вариант без копирования. Вообще нативное копирование работает очень даже быстро. Тому пример ArrayList, который даже с копирование в среднем случае работает быстрей LinkedList'а.
Скачки видны до этого, а если бы мы их добавили, то сложно было бы смаштабировать результаты в читабельный график (Да и памяти у нас под Штрассена не много).
Гарантий я дать не могу. Но думаю, что асимптотически расспараллеленный Штрассен будет работать быстрей с точки зрения математики. На практике же существуют ограничения, например, из-за своей рекурсивной природы алгоритму требуется много памяти, и на предельных загрузках многое будет зависить от GC (Мы же всё таки говорим о реализации под JVM), да и число ядер у нас не бесконечное число т.д. и т.п… Поэтому не нужно считать это панацеей. В нашей случае, мы использовали средненькие по производительности ноутбуки с выделением 8 ядер и оперативной памяти порядка 4-6гб под jvm. GC работал на пределе. И ясно, что проверить реализации у нас не получится на матрицах размерностью 8_000 и более в силу ограничений на железо.
Что Вы понимаете под набором матриц?
В каждом тесте работа велась только с одной матрицей определенной размерности. Дальше матрицы с шагом в 100 увеличивали свою размерность. Алгоритм Штрассена выделяет подматрицы и каждую такую подматрицу можно и нужно расспараллеливать на вычисление. А вот как выделить подматрицы в обычном алгоритме и можно ли это в принципе… я лично не знаю(отношусь скептически):)
*Опечатался*
И в общем случае получается, что переумножать матрицы размером, например, в 1200*1200 и 2000*2000 — нет, просто нет Разницы, они расширяются до 2048.
Всё же сравнивать с нативными отклаженными годами библиотеками будет не совсем корректно. Переписывать всё на С/С++ желания и времени, к сажалению, нет(
НО! Раз наша статья получила такой резонанс(Мы ожидали меньшего), то появилась идея обощить принципы решения подобных типов задач и, например, взять к и попробовать всё это дело на СКЦ(Суперкомпьютерном центре) Политехнического Университета СПб. Дело тут уже состоит в том, чтобы убедить высокопоставленных людей, что подобного рода задач интересны и важны, тогда получим доступ к очень серьёзным ресурсам. Надеюсь я Вы меня правильно поняли, большое спасибо за комментарий к нашей работе! :)
1. Тестировалось все на обычных ноутбуках c i5-i7 и 6gb оперативной памяти(ноутам 3-4 года).
2. Да вы всё правильно понимаете, дело в том, что да, дело в степени двойки:)… Алгоритм работает с квадратными матрицами и из сего следует, что при размерах в 1025*1025 матрица увеличивается до 2048*2048, так же если размер матрицы 1500*1500, то матрица всё также увеличивается до размерности в 2048. Вот и происходит 7 кратный взрыв при переходе с одной степени 2 к другой. И в общем случае получается, что переумножать матрицы размером, например, в 1200*1200 и 2000*2000 — нет, просто нет.(при расширении она дополняется нулями)
Спасибо за комментарий и обратную связь!
Information
Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
Спасибо за Ваш интерес.
P.S. кст, Вы один из тех, из-за кого наш преподаватель отменил занятие(из-за Joker), так что, возможно, если бы не Вы, то этой статьи и не было бы:))
В нашем исходном коде всё ок. Валидация проверит корректность размерностей матриц да и не только это.
Спасибо за такое внимание!
А кто сказал, что реализация работает медленно?) Просто есть противоречия в словах. То память расходуется не правильно, то в джавовское управление памятью не замедляет алгоритм. Если есть конкретные идеи, то предлагайте. А то это перерастает в какой-то холивар)
Что касается копирования, да их тут много. Подобные алгоритмы в принципе решаются на других языка, где имеется соответсвующая гибкость работы с памятью. Мы же говорим про реализацию только на Java.
Спасибо за Ваши советы!
В нашей статье есть ссылка на другую хабра-статью с траспонированием и там сказано, что в Фортране не потребуется делать траспонирование и обычный алгоритм будет работать в разы быстрей и кэшем всё тоже ок.
Спасибо за Ваш интерес!)
P.S. «magic» я упомянул с иронией, не более
Предложите вариант без копирования. Вообще нативное копирование работает очень даже быстро. Тому пример ArrayList, который даже с копирование в среднем случае работает быстрей LinkedList'а.
Скачки видны до этого, а если бы мы их добавили, то сложно было бы смаштабировать результаты в читабельный график (Да и памяти у нас под Штрассена не много).
В каждом тесте работа велась только с одной матрицей определенной размерности. Дальше матрицы с шагом в 100 увеличивали свою размерность. Алгоритм Штрассена выделяет подматрицы и каждую такую подматрицу можно и нужно расспараллеливать на вычисление. А вот как выделить подматрицы в обычном алгоритме и можно ли это в принципе… я лично не знаю(отношусь скептически):)
Странно, что нет функционала по редактированию своих же комментариев( много опечаток
И в общем случае получается, что переумножать матрицы размером, например, в 1200*1200 и 2000*2000 — нет, просто нет Разницы, они расширяются до 2048.
НО! Раз наша статья получила такой резонанс(Мы ожидали меньшего), то появилась идея обощить принципы решения подобных типов задач и, например, взять к и попробовать всё это дело на СКЦ(Суперкомпьютерном центре) Политехнического Университета СПб. Дело тут уже состоит в том, чтобы убедить высокопоставленных людей, что подобного рода задач интересны и важны, тогда получим доступ к очень серьёзным ресурсам. Надеюсь я Вы меня правильно поняли, большое спасибо за комментарий к нашей работе! :)
Спасибо за отзыв)
2. Да вы всё правильно понимаете, дело в том, что да, дело в степени двойки:)… Алгоритм работает с квадратными матрицами и из сего следует, что при размерах в 1025*1025 матрица увеличивается до 2048*2048, так же если размер матрицы 1500*1500, то матрица всё также увеличивается до размерности в 2048. Вот и происходит 7 кратный взрыв при переходе с одной степени 2 к другой. И в общем случае получается, что переумножать матрицы размером, например, в 1200*1200 и 2000*2000 — нет, просто нет.(при расширении она дополняется нулями)
Спасибо за комментарий и обратную связь!