Andreiwse

Поиск соседних ячеек в неструктурированой сетке

Здравствуйте!
 

Пользуюсь сеткой в формате .NEU - габитовский формат. Данный формат как и другие мне известные имеет следующую структуру:

Матрица точек
номер точки1 - координаты точки1 
.

.
номер точкиN - координаты точкиN
 

 

Матрица ячеек 
номер ячейки1 - номера точек из которых состоит ячейка1

.

.
номер ячейкиМ - номера точек из которых состоит ячейкаМ
где N- кол-во точек, M - кол-во ячеек.  

Мне нужна следующая информация: для каждой ячейки знать номера ячеек с которыми она контактирует. Для этого я сравниваю каждую ячейку со всеми остальными ячейками, то есть каждую строку матрицы ячеек со всей матрицой ячеек. Получается два цикла один вложенный в другой в общем M^2 сравнений, расчет занимает очень много времени. 

Вопрос1  Есть ли способы ускорение расчета нужной мне информации?
Вопрос2  Есть ли форматы сеток в которых эта информация есть в явном виде?

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах


Мне нужна следующая информация: для каждой ячейки знать номера ячеек с которыми она контактирует

Для чего?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, Вам надо универсальное решение, или только конкретно для этой сетки?

Как бы кубик с полостью построил. Отдельно 1915 тетраэдров. Чешу репу над тем, как вычислять соседей среди них. Если только для этой задачи, то может и можно будет победить, увы чуть не вручную. А если же все-таки нужен универсальный алгоритм, чтоб прям на основе исходного файла и новый файл статистики со всеми раскладами, - пасую. :flush:

Наверно вам правильно @piden намекнул, что не для этого форума вопрос. Очевидно в мире есть какие-то оптимизированные алгоритмы для тетраэдров. Шукать трэба. 

И не совсем ясно причем тут газодинамика, гидродинамика и теплообмен.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Делаете свой решатель? Тогда лучше искать информацию на иноязычных ресурсах.

Да, я делаю свой решатель. 

За ссылку спасибо, в есть кое что полезное. 

 

@Andreiwse, Вам надо универсальное решение, или только конкретно для этой сетки?

Как бы кубик с полостью построил. Отдельно 1915 тетраэдров. Чешу репу над тем, как вычислять соседей среди них. Если только для этой задачи, то может и можно будет победить, увы чуть не вручную. А если же все-таки нужен универсальный алгоритм, чтоб прям на основе исходного файла и новый файл статистики со всеми раскладами, - пасую. :flush:

Наверно вам правильно @piden намекнул, что не для этого форума вопрос. Очевидно в мире есть какие-то оптимизированные алгоритмы для тетраэдров. Шукать трэба. 

И не совсем ясно причем тут газодинамика, гидродинамика и теплообмен.

Не стоит Ваше время на реализацию поиска соседей используя данный формат. 

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

 

 

 

 

"И не совсем ясно причем тут газодинамика, гидродинамика и теплообмен" - а где лучше об этом спросить, просто область моей задачи из газодинамики, вот я спросил сюда. 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
В каких сеточных форматах есть именно то, что мне нужно в готовом виде

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

Или попробуйте связаться с @HFL, он занимается in-house кодами.

Изменено пользователем piden

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Формат который мне нужен, я сам получаю из формата .NEU,  - то есть у меня есть понимание что мне  нужно. Но это мне не помогает. 

Если ВЫ знаете другие форматы, пишите в лоб как есть,  :smile:

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я вообще-то без иронии сказал. Опишите, как должен выглядеть удовлетворяющий Вас формат. Номера ячеек сгруппированы по соседству? Или в конце дается длинный список, какая с какой сопрягается и через какой фейс? Мне правда интересно.

 

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

Изменено пользователем piden

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я вообще-то без иронии сказал. Опишите, как должен выглядеть удовлетворяющий Вас формат. Номера ячеек сгруппированы по соседству? Или в конце дается длинный список, какая с какой сопрягается и через какой фейс? Мне правда интересно.

 

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

Да, я попробовал все форматы из Poinwise, я ничего не нашел.

Мне нужно что бы для тетраэдральной сетки была следующая матрица:

1   23 44 67 89

2   34  7  99 55

3  12  14 33 45

.

.

Где первая колонка это номера ячеек, четыре остальные колонки это номера соседних ячеек для данной ячейки. Например, ячейка 1 контактирует с ячейками 23 44 67 89. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, Дык еще ж контакт могёт быть разным. В вершинке, аль фейсом? А ежели соседей менее четырех?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, Дык еще ж контакт могёт быть разным. В вершинке, аль фейсом? А ежели соседей менее четырех?

Контакт в моем случае это фейсом, и поэтому для каждой тетраидальной ячейки может быть только 4 соседа, если эта ячейка не является граничной. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Может я не очень понял, но почему нельзя однократно до расчета обработать эту сетку, найти всех соседей ячеек, запомнить их в структуре, как вам удобно, и потом уже проводить расчеты?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, есть в Mathematica конекшн к TetGen. На примерах из справки работает чики-пики. И картинки рисует и соседей вычисляет. А вот, как ни бился, не смог скормить математике точки из примера с кубиком. :no:

Соседи не поддаются, но хотя бы геометрия строится в Rhino, уже позитивчик :smile:

0_cd92e_eadc8efb_orig.png

Изменено пользователем Blurp

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

@Andreiwse, есть в Mathematica конекшн к TetGen. На примерах из справки работает чики-пики. И картинки рисует и соседей вычисляет. А вот, как ни бился, не смог скормить математике точки из примера с кубиком. :no:

Соседи не поддаются, но хотя бы геометрия строится в Rhino, уже позитивчик :smile:

0_cd92e_eadc8efb_orig.png[

Есть ограничения, я могу пользоваться только своим кодом.

благодарю Вас за попытку помочь.  

Поделиться сообщением


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

Понимаю.

Ответно благодарю вас за то, что заставили пошевелить мозгами. Хоть задачу не решил, но залез в такие дебри....вплоть до попыток прикрутить для решения MySQL сервер, либо файловую БД SQLite :biggrin: Но, увы, в SQL запросах не силен  :no_1:

А так, на всякий случай, если заинтересуетесь, то SQLite халявна. 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

В принципе и TetGen фриварный. И, по идее, функцию поиска соседей оттуда можно утянуть.
А так, нашел еще тут в PDFке одной упоминание про какой-то генератор Pyramid и что якобы он информацию о соседях пишет в аутпут-файло, но более про этот генератор ничего не раскопал. :no:
 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Или попробуйте связаться с @HFL, он занимается in-house кодами.

Могу рассказать как это сделано у нас (не претендуя на универсальность рецепта)

 

Стандартный сеточный формат (у нас  это IDEAS Universal -  *.unv ) используется только для импорта сетки из препроцессора в решалку. В самой решалке используется внутренний формат. Там в структуре, которая соответствует расчетной ячейке (или КО в случае FVM) содержаться указатели на соседние KO (6 штук для гексы или 4 для тетры) которые инициализируются при загрузке сетки из внешнего сеточного формата во внутренний один раз при загрузке.  Сама процедура инициализации распараллелена (есть как MPI так и GPU версии) что значительно ускоряет процесс инициализации, но сам алгоритм похож на ваш.  Время полной инициализации от секунд (если расчетная область целиком влазит в память GPU) до десятков минут для сеток >30млн (общий размер расчетной области при этом примерно 40-60 Гб). 

Может я не очень понял, но почему нельзя однократно до расчета обработать эту сетку, найти всех соседей ячеек, запомнить их в структуре, как вам удобно, и потом уже проводить расчеты?

Потому что судя по всему человек делает это первый раз в жизни  :smile: Это нормально. По этим всем граблям нужно пройти лично  :biggrin:

Изменено пользователем HFL

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Могу рассказать как это сделано у нас (не претендуя на универсальность рецепта)

 

Стандартный сеточный формат (у нас  это IDEAS Universal -  *.unv ) используется только для импорта сетки из препроцессора в решалку. В самой решалке используется внутренний формат. Там в структуре, которая соответствует расчетной ячейке (или КО в случае FVM) содержаться указатели на соседние KO (6 штук для гексы или 4 для тетры) которые инициализируются при загрузке сетки из внешнего сеточного формата во внутренний один раз при загрузке.  Сама процедура инициализации распараллелена (есть как MPI так и GPU версии) что значительно ускоряет процесс инициализации, но сам алгоритм похож на ваш.  Время полной инициализации от секунд (если расчетная область целиком влазит в память GPU) до десятков минут для сеток >30млн (общий размер расчетной области при этом примерно 40-60 Гб). 

Потому что судя по всему человек делает это первый раз в жизни  :smile: Это нормально. По этим всем граблям нужно пройти лично  :biggrin:

Если я правильно понял. И у Вас и у меня по сути реализован конвертор формата из стандартного (unv, neu) в свой формат. Я тоже это делаю один раз для одной сетки. 

У меня без паралелеливания 400 тыс ячеек считает за 4 часа. А у Вас во сколько раз паралеливание дало выигрыш?

 

Изменено пользователем Andreiwse

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Если я правильно понял. И у Вас и у меня по сути реализован конвертор формата из стандартного (unv, neu) в свой формат. Я тоже это делаю один раз для одной сетки. 

У меня без паралелеливания 400 тыс ячеек считает за 4 часа. А у Вас во сколько раз паралеливание дало выигрыш?

 

По сути выигрыш равен числу параллельных потоков (в разах). То есть при распараллеливании у вас сложность будет не O(N^2) а O((N^2/n)) ... на самом деле выигрыш у нас еще больше из за алгоритмических ухищрений, связанных с порядком хранения структур (но это внутренняя кухня, которая работает только в частном случае)

 

То есть при использовании GPU это тысячи раз, при использовании MPI от десятков до сотен раз.

 

Ниже пример с куском выхлопа решалки.

7 внешних сеток, общий объем расчетной области ~24 млн. КО, при инициализации использовалось 160 ядер

 

Init HyperFLOW3D Solver time=965.836sec.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

GPU, multithreading....

Только хардкор! :biggrin:

0_cd9d3_72b0d9a4_orig.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Хардкоры ? Их есть у меня  :biggrin:

 

Сетка чуть больше 5млн. 

Время инициализации ~ 15 сек

 

3Tflop/s в даблах они такие  :rolleyes:

post-34943-0-41268800-1446831807.png

2 пользователям понравилось это

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Против Кеплер лома нет приема.
:flush::smile:

Но тему копать интересно тем не менее.
Пока ускорился аж в 10 раз. :biggrin: Целых 20 ячеек/сек для геометрии из 4-го поста. driving.gif
Не представляю, что будет при задаче размерностью 100K, наверное все загнется к едрене фене. Но приятно ощутить себя чуточку программистом :smile:

0_cd9e2_c1025b78_orig.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
В 02.11.2015 в 20:20, Andreiwse сказал:

400 тыс ячеек считает за 4 часа

105 мин :wallbash:

0_dd2d1_e1e65ee3_M.png0_dd2d2_78f0965b_M.png

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте аккаунт или войдите для комментирования

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

Создать аккаунт

Зарегистрируйтесь для получения аккаунта. Это просто!


Зарегистрировать аккаунт

Войти

Уже зарегистрированы? Войдите здесь.


Войти сейчас

  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу



  • Реклама

  • Сообщения

    • streamdown
      Участвовал я как-то в создании ноутбука промышленного. Прям как для военных (это была первая целевая аудитория). Так там было КБ, ресурсы производства, связи, выставки (на которые можно было попасть только благодаря связям  ). Там были нехилые финансовые вливания даже на уровне проектирования (да-да...кадэшэчка, модельки, сборки), чего уж говорить обо всём остальном. И не срослось, ибо после первой же выставки...никто не заинтересовался)))) И не потому что не получилась "железка" (сработано было на ура, я б сам себе такой купил если б деньги были на это), а потому что - не тем военным показывали, и не тем гражданским. (вспоминаем вышеозвученные слова и буквы "PR + SMM + наверное, GR" ) Дык не с того начал! При наличии хоть какой-то вменяемой идеологии, маркетинга, и прочего "гуманитария" ))) я б тоже в бой ринулся (а кому не охота увековечить себя в летах). А так просто...замоделируй и просчитай заведомую "работу в стол" ... не.
    • MFS
      Работы много. Помнится тут человек вкинул идею на счет помощи детям с ДЦП: разработать раскрой для ходунков или кресла. Я ему писал потом, предлагал что-то поделать (у меня была возможность), но товарищ, похоже, скис не начав. Тут замах на несколько порядков сложнее...посмотрим.
    • streamdown
      До сих пор топикстартер так и не смог сформулировать свою роль (и свой конкретный род занятий) в своём проекте)))   Хмм...знаю лично одного довольно успешного фандрайзера (проще загуглить, чем тут описать деятельность). Так вот у него нет каких-либо "посиделок за столом". Там пипец работа гуманитария во всей красе. Он и образованием даже профильным высшим наделён, и даже не одним. Так вот, о чём я: создание техники подобного уровня и для подобных целей - это пипец какая непростая задача даже с точки зрения нетехнического персонала.
    • Клиент
    • elanium
      Коллеги, я думаю, что вопрос малой памяти в целесообразности. Фанук - японцы. Весь их уклад таков. Посмотрите на машины американцев - в них шаровая это ШАРОВАЯ! Кузов - КУЗОВ. Японцы - много авто с объемом движка меньше 0,2 литра! Так и с памятью. Удобство, конечно, не на первом месте, но варианты для работы есть. @Владимир56 вот умеет использовать знания для удобства - умеет программировать так, что удобно работать. Память сама по себе дорогая и в цене практически не падает. И что-то про Сименс все молчат, там с памятью вопрос решён?
    • imt
        Вроде описал?...   В локальной системе координат картинка НДС получается, нагляднее что ли. Удобно смотреть, компоненты напряжений, деформаций и т.п.   В принципе средствами ВБ это, наверное, решается: 1. Создать ЛСК, соответствующие каждому положению механизма 2. Задать ограничения в каждой ЛСК 3. На каждом шаге оставить активным только одно ограничение. Получается громоздко и трудоемко.   Забыл сказать, задача нелинейная с контактом. Надо посмотреть, в том числе распределение напряжений в пятне контакта в паре "ось- втулка" при работе механизма.       Хочется добавить в ВБ командную вставку - не знаю как...
    • LiViS
      Это колун, который будет колоть большие деревянные колоды. Это колун, который будет колоть большие деревянные колоды.  
    • MFS
      Стадия да, сильно допосевная. По уму тут уже в заголовке темы должен быть патентный поиск + обзор конкурирующих решений + свои идеи - работы - то на пару-тройку дней, но ТС и этим не озаботился.
    • piden
      Так может стоит описать, какую цель преследуют все манипуляции?
    • imt
      Надо бы закрепить ...