Если бы у меня был доступ к потенциально большому количеству процессоров и я хотел бы быстро проверить простоту 100 миллионов цифр на простоту, используя архитектуру уменьшения карты, сколько процессоров мне потребуется? Каждый из отображенных вычислительных экземпляров будет выполнять эффективные проверки против рассматриваемого числа с назначенным диапазоном делителей (например, Экземпляр 1: проверяет делители 2-1000, Экземпляр 2: проверяет делители 1001-2000 и т. Д.).
Определения:
быстро означает проверку единичного делителя на 100 миллионов цифр в течение 30-60 минут.
эффективное подразделение означает только проверку нечетных чисел до квадратного корня. Младшие делители будут только известными простыми числами для ускорения вычислений.
1 процессор это эквивалентная мощность процессора 1.0–1.2 ГГц процессора Opteron 2007 или 2007 Xeon.
Да, я знаю, что есть алгоритмы получше, такие как AKS, но мне нужно иметь возможность разделить работу между сопоставленными экземплярами.
Вероятно, лучше задать вопрос: какова математическая связь между количеством процессоров и количеством времени, которое требуется для проверки числа с заданной величиной цифр?
Я спрашиваю об этом, потому что пытаюсь подсчитать количество экземпляров Map_Reduce, которые мне нужно будет купить на Amazon AWS, чтобы сделать вычисления выполнимыми (пара месяцев / менее года).
Математической связи нет. Это полностью зависит от вашего программного обеспечения, архитектуры машины, которую вы получаете. Какая оперативная память, диск, точные характеристики процессора, такие как кэш L2 / 3, могут иметь большое влияние на производительность. По сути, вам нужно будет сделать сравнительно небольшой тест, а затем вычислить цифры.
Я полностью согласен с @Zypher, но вот вам еще одна идея. Если вы хотите сделать эту задачу рентабельной, вы можете рассмотреть возможность использования для нее графических процессоров через CUDA, OpenCL и тому подобное. Несмотря на то, что первоначальные инвестиции могут быть значительными, в долгосрочной перспективе они будут намного дешевле, чем использование Amazon.