Стоимость поиска в сравнении с расчетами

12

Я заинтересован в настройке вычислений для проверки соответствия критерию расстояния: расстояние между вектором и вектором пыльника x j должно быть меньше некоторого значения r m a x . Мои данные разделены по ортогональной сетке координат. Поскольку моя отсечка меньше расстояния между конечными точками координат ближайшего соседа, я бы хотел добавить переменную «октант», чтобы проверить, правильно ли все настроено:xixjrmax

if octant[j] in allowed_list continue

как "короткое замыкание"

if dist(x[i], x[j]) < r_max

Мой вопрос: насколько вычислительно эффективны логические поиски и сравнения относительно операций с плавающей запятой? Стоит ли это делать на современных архитектурах?

aeismail
источник
3
Хотели бы вы разветвить свой код и протестировать его? Я чувствую себя стандартным ответом на большинство из них: «Лучше кодировать это (в одну сторону) или (как-то иначе)?» Типы вопросов: «Попробуйте и сравните».
Джефф Оксберри
1
Просто мои 2 цента. Как писал Джефф, такого рода советы я всегда получал, когда задавал похожие вопросы о стековом потоке в отношении кода C ++: сначала все кодируй, организуй код так, чтобы я оставался модульным и многократно используемым, и только потом начинай рефакторинг. Существует правило 80-20: программное обеспечение тратит 80% времени на 20% кода. Подождите, пока структура не
взойдет
@GeoffOxberry: Мой вопрос не настолько конкретен: я просто хочу знать, есть ли преимущество аппаратного обеспечения или компилятора, которое дает логическая проверка по сравнению с операцией с плавающей запятой.
aeismail
3
Но ваш вопрос слишком общий. Никто не может сказать, не увидев какой-то конкретный код. Практическое правило гласит, что даже лучшие программисты не могут определить узкие места своего кода без профилирования. Я провел последние 25 лет в программировании, и я знаю, что это правда для меня.
Вольфганг Бангерт

Ответы:

15

Мое эмпирическое правило заключается в том, что если вы можете эффективно вычислить некоторое количество (хорошее использование FPU) менее чем за 50 флопс на значение двойной точности, то лучше пересчитать, чем сохранить. Тенденция, которая была устойчивой в течение десятилетий, заключается в том, что способность с плавающей запятой улучшаться быстрее, чем производительность памяти, и вряд ли ослабнет из-за физических ограничений и энергетических потребностей быстрой памяти. Значение 50 имеет правильное значение для всех популярных вычислительных платформ (Intel / AMD, Blue Gene и GPU).

Приблизительная смета расходов на ядро

[Рекомендации для 2011/2012 машин на базе процессоров Intel и AMD]

  • 0.05
  • 0.2
  • 0.4
  • 0.40.8
  • 2
  • 35
  • 35
  • 5
  • 48
  • 12
  • 12
  • 3050
  • 100
  • 1031 μ
  • 10410 μ
  • 106
  • 2106MPI_Allreduce
  • 107
  • 5108
  • 1.81012

дальнейшее чтение

Джед браун
источник
Я нашел эту информацию действительно полезной. Кстати, откуда вы взяли эти данные? Я ищу ссылки для цитирования.
Эльдила