Какие алгоритмы имеют высокую временную сложность, чтобы помочь «сжечь» больше циклов процессора?

Question

Я пытаюсь написать демо для встроенного процессора, который является многоядерной архитектурой и очень быстр в вычислениях с плавающей запятой.Проблема в том, что у меня есть текущее аппаратное обеспечение - процессор, подключенный через оценочную плату, где скорость DRAM к чипу несколько ограничена, а скорость платы к ПК очень медленная и неэффективная.

Таким образом, при демонстрации большогоУмножение матриц, я могу сделать, скажем, 128x128 матриц за пару миллисекунд, но ввод / вывод занимает (много) секунд, убивает демо.

Итак, я ищу какой-то расчет счем выше сложность, чем n ^ 3, тем лучше (но желательно, чтобы ее было легко программировать и объяснять / понимать), чтобы вычислительная часть была более доминирующей в временном бюджете, где набор данных предпочтительно привязан к 16 КБ на поток (ядро).

Любое предложение?

PS: Я думаю, что это очень похоже на этот вопрос по своей сути.

Answer 1

Вы можете генерировать большие (256-битные) числа и разбивать их;это обычно используется в инструментах «стресс-тест».Если вы специально хотите выполнять вычисления с плавающей запятой, вы можете создать базовый симулятор n-body с интегратором Runge-Kutta и запустить его.

Answer 2

Вы можете сделать наименьшее количество квадратов.Одним из применений этого является выявление выбросов в наборе данных.Например, вы можете сгенерировать выборки из некоторой гладкой функции (скажем, многочлена) и добавить (большой) шум к некоторым из выборок, и тогда проблема заключается в том, чтобы найти подмножество H выборок заданного размера, которое минимизирует суммуквадраты остатков (для многочлена, подогнанного к образцам в H).Поскольку таких подмножеств существует большое количество, у вас есть множество подходов!Есть приблизительные алгоритмы для этого, например здесь .

Answer 3

PageRank может подойти. Сформулированная как задача линейной алгебры, каждый неоднократно возводит в квадрат некоторую матрицу с плавающей точкой контролируемого размера до сходимости. В графической метафоре одно изменение «ряби» проникает в каждый узел на другие ребра. Обе процедуры можно проводить параллельно.

Answer 4

Что вы можете сделать, это

1. Объявить std :: vector of int
2. заполнить его от N-1 до 0
3. Теперь продолжайте использоватьstd :: next_permutation до тех пор, пока они не будут снова отсортированы, i..e..next_permutation возвращает false.

С N целыми числами для этого потребуется O(N !) вычисления, а также детерминистический

Answer 5

Другой идеей может быть вычисление фрактальной карты.В основном, выберите сетку любой размерности, которую вы хотите.Затем для каждой точки сетки выполните фрактальную итерацию, чтобы получить значение.Некоторые точки могут потребовать всего несколько итераций;Я полагаю, что некоторые будут повторяться вечно (хаос; конечно, это не может произойти, когда у вас есть конечное число чисел с плавающей точкой, но все же).Те, которые не останавливаются, вам придется «обрезать» после определенного количества итераций ... просто сделайте это нелепо высоким, и вы сможете продемонстрировать высококачественную фрактальную карту.

Еще одним преимуществом этого является то, что ячейки сетки обрабатываются полностью независимо, поэтому вам никогда не понадобится осуществлять связь (даже на границах, как в вычислениях трафарета, и определенно не O (попарно), как при прямом моделировании N-тела).Вы можете с пользой использовать O (gridcells) число процессоров, чтобы распараллелить это, хотя на практике вы, вероятно, сможете получить лучшее использование, используя gridcells / factor-процессоры и динамически планируя точки сетки для процессоров на основе готовности.Вычисления в основном все математические с плавающей точкой.

Мандельброт / Юлия и Люпанов приходят на ум в качестве потенциальных кандидатов, но любой должен делать.

Answer 6

Ну, одним из способов было бы внедрить решатель грубой силы для задачи коммивояжера в некотором M-пространстве (с M> 1).

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

Для N точек существует (N!) Перестановок (с коэффициентом избыточности не менее (N-1), но помните, что оптимизация отсутствует). Каждая пара точек требует (M) вычитаний, (M) умножений и одной операции с квадратным корнем, чтобы определить их пифагорейское расстояние. Каждая перестановка имеет (N-1) пар точек для вычисления и добавления к общему расстоянию.

Таким образом, порядок вычислений равен O (M ((N + 1)!)), А объем памяти - только O (N).

Кроме того, это не должно быть ни слишком сложным, ни слишком интенсивным для распараллеливания между ядрами, хотя это требует некоторых накладных расходов. (Я могу продемонстрировать, если это необходимо).