Проблема закона Мура [закрыто]

Предположим, вам нужно запустить программу на самом быстром в мире суперкомпьютере, выполнение которого займет 10 лет. Вы могли бы:

  • Потратьте 250 миллионов долларов сейчас
  • Программа на 9 лет, ускорение закона Мура (в 4000 раз быстрее), потратить 1 миллион долларов за 10 лет, завершить за 2 недели.

Какова оптимальная стратегия?

Вопрос из раздела «Тенденции долгосрочного хранения и вы »

10.12.2008 14:24:41
12 ОТВЕТОВ
РЕШЕНИЕ

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

У нас есть четыре уравнения (на самом деле два из них являются функциями):

  1. endtime(startyear) = startyear + (calculations / speed(startyear))
  2. speed(year) = speed(year-1.5)4 (проблема предполагает, что аппаратное и программное обеспечение удваивается по скорости каждые 18 месяцев)
  3. endtime(0) = 0 + (calculations/speed(0)) = 10 years
  4. speed(0) = calculations/(10 years) (подразумевается под № 3)

Я начал использовать производные, чтобы минимизировать конечное время, но понял, что плохо помню свои дифференциальные уравнения. Таким образом, я преобразовал # 2 в эквивалентную формулу экспоненциального роста :

speed(year) = speed(0)*4(год / 1,5) = (calculations/10)*4(год / 1,5)

Затем я написал этот маленький скрипт BeanShell:

calculations() {
    return 10000000; // random constant (gets cancelled out anyway)
}
speed(year) {
    speed0 = calculations()/10; // constant factor
    return speed0*Math.pow(4.0, year/1.5);
}
endtime(startyear) {
    return startyear + calculations()/speed(startyear);
}
findmin() {
    start = 0.0;
    finish = 10.0;
    result = 0.0;
    // home in on the best solution (there should only be one minimum)
    for (inc = 1; inc > 0.00000001; inc /= 2.0) {
        result = findmin(start,finish,inc);
        start = result-2*inc;
        finish = result+inc;
    }
    print("Minimum value is " + result + ", taking a total of " +
            endtime(result) + " years");
}
findmin(start,finish,inc) {
    lastNum = 0;
    lastVal = Double.MAX_VALUE;
    for (i = start; i < finish; i += inc) {
        result = endtime(i);
        if (result > lastVal) {
            print("Minimum value between " + start + " and " + finish +
                    " is " + lastVal + ", occurring at " + lastNum);
            return i;
        }
        lastNum = i;
        lastVal = result;
    }
    return lastNum;
}

Вывод:

bsh % source("moore.bsh");
bsh % findmin();
Minimum value between 0.0 and 10.0 is 3.5749013123685915, occurring at 2.0
Minimum value between 1.0 and 4.0 is 3.4921256574801243, occurring at 2.5
Minimum value between 2.0 and 3.5 is 3.4921256574801243, occurring at 2.5
Minimum value between 2.25 and 3.0 is 3.4886233976754246, occurring at 2.375
Minimum value between 2.25 and 2.625 is 3.488620519067143, occurring at 2.4375
Minimum value between 2.375 and 2.5625 is 3.488170701257679, occurring at 2.40625
Minimum value between 2.375 and 2.46875 is 3.488170701257679, occurring at 2.40625
Minimum value between 2.390625 and 2.4375 is 3.488170701257679, occurring at 2.40625
(snip)
Minimum value between 2.406149387359619 and 2.4061494767665863 is 3.4881706965827037,
occurring at 2.4061494171619415
Minimum value is 2.4061494320631027, taking a total of 3.488170696582704 years

Таким образом, с учетом предположений, которые я высказал ранее, ответ заключается в том, чтобы подождать 2.406149 ... лет (или примерно 2 года, 148 дней , согласно Google).


Изменить: я заметил, что со второй формулой, переписанной, как указано выше, решение требует только простого исчисления.

endtime(x) = x + c/speed(x) (where c = calculations)
speed(x) = speed(0) * 4^(x/1.5) = (c/10)*4^(2x/3)
=> endtime(x) = x + c/((c/10)*4^(2x/3))
              = x + 10*(4^(-2x/3))
d/dx endtime(x) = 1 + 10*ln(4)*(-2/3)*(4^(-2x/3))

Критическая точка - это когда d / dx = 0, поэтому

1 + 10*ln(4)*(-2/3)*(4^(-2x/3)) = 0
=> 4^(-2x/3) = 1/(10*ln(4)*(2/3))

Возьмем log4 с обеих сторон: (помните, что log4 (x) = ln (x) / ln (4) и что ln (1 / x) = -ln (x) )

-2x/3 = ln(1/(10*ln(4)*(2/3))) / ln(4)
      = -ln(10*ln(4)*2/3) / ln(4)
=> x = (-3/2) * -ln(1/(10*ln(4)*2/3)) / ln(4)
     = 3*ln(10*ln(4)*(2/3)) / 2*ln(4)

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

(Я должен отметить, что это просто критическая точка, а не обязательно минимум. Но вторая производная (которая имеет форму -(some constant)*4-2x / 3 ) всегда отрицательна. Таким образом, функция всегда вогнута, поэтому единственная критическая точка минимум.)

7
11.12.2008 22:00:24

Но закон Мура не ускоряет программирование.

9 лет программирования никогда не будут сведены к 2 неделям.

Полагаю, если вы не потратите 9 лет на программирование автоматизированного устройства для чтения мыслей.

0
10.12.2008 14:32:33

Потратьте деньги сейчас - цена / стоимость доллара сейчас по сравнению с оценкой за 10 лет - все равно что пытаться прогнозировать погоду через 3 месяца. Кроме того, в нем не учитываются такие факторы, как тенденции программирования за 10 лет и то, будут ли вещи на самом деле в 4000 раз быстрее или в 4000 раз более масштабируемыми / параллельными, что кажется тенденцией последнего времени.

Кроме того, по словам майя, конец света наступит в 2012 году, так что проводите добычу сейчас!

1
10.12.2008 14:33:41

Программа на 4 года, а затем запустить его в 2,5?

(Я уверен, что есть "идеальный" ответ где-то между 4 и 5 годами ...)

0
10.12.2008 14:34:03

Закон Мура не о скорости, а о количестве транзисторов в данной области кремния. Нет гарантии, что через 9 лет скорость увеличится в 4000 раз. Во всяком случае, в последние годы частота ГГц выровнялась. В настоящее время увеличивается количество ядер в процессоре.

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

11
3.07.2012 14:09:39

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

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

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

0
10.12.2008 14:35:28

Упростите модель, чтобы сделать оценку, которую вы можете запустить сейчас. По мере появления большего / лучшего ресурса уточняйте модель для получения более точных результатов.

1
10.12.2008 14:36:34

Убедитесь, что ваша программа может приостановить и продолжить работу, а затем поставить ее на все более быстрые машины по мере их появления. Лучшее из обоих миров...

3
10.12.2008 14:37:05
Если вам не придется платить за каждую более быструю и быструю машину ... Тем не менее, хороший совет. Когда в последний раз вы видели, как компьютер работал 10 лет без простоев?
Mark Ransom 11.12.2008 22:24:50
У меня никогда не было такого последнего, лично. Но недавно мне пришлось перезагрузить тот, который длился год.
Jonathan 22.12.2008 20:45:01

Самый быстрый способ сделать это:

  • Напишите версию для текущей технологии, которая может быть перенесена в каждое новое поколение.
  • Наряду с миграциями продолжайте программировать любые улучшения алгоритмически и т. Д.

Самый дешевый способ, очевидно, состоит в том, чтобы оставить его подольше. Вам нужно учитывать время программирования (которое было бы достаточно постоянным).

Кроме того, я не хотел бы делать слишком большую ставку на продолжение закона Мура.

Также помните, что закон Мура относится к плотности транзисторов, а не к скорости вычислений для конкретной проблемы. Даже если вычислительная мощность в целом значительно возрастает, это не обязательно означает, что ваше приложение выиграет.

1
10.12.2008 14:37:24

Закон Мура касается количества транзисторов, которые будут размещены в одном чипе, и не относится к скорости микропроцессоров в целом.

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

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

4
10.12.2008 14:38:27

Это делает ошибочное предположение, что закон Мура на самом деле является законом. Вероятно, лучше назвать Теорию Мура. Риск, которого вы ожидаете, заключается в том, что через 10 лет все еще может пройти 10 лет. Запустите программу сейчас (со встроенной паузой и перезапуском, если это возможно), начните команду, ищущую другие способы решить проблему, которая будет быстрее. Если у вас есть уверенность в том, что один или другой предоставит более быстрое решение, переключитесь.

РЕДАКТИРОВАТЬ : Как проблема, я думаю, что лучшее значение в этом вопросе заключается в том, что он заставляет вас проверить, являются ли ваши предположения обоснованными. Очевидное решение - поскольку в соответствии с определением проблемы вы получаете тот же результат за то же время с меньшими затратами денег - это ожидание, но это зависит от некоторых неявных предположений. Если эти предположения не верны, то очевидное решение не обязательно является лучшим, как свидетельствуют многие ответы здесь.

0
10.12.2008 14:57:45

В вопросе указано, что проблема запускается на суперкомпьютере, поэтому проблема должна быть векторизованной. Скорость суперкомпьютеров растет значительно быстрее, чем закон Мура, поэтому в зависимости от реальной проблемной области одним из подходов было бы нанять хакерских бандитов для создания всемирно распространенного червя Уорхола, который приобрел ресурсы 85% компьютеров. в сети для короткой распределенной сетки, подобной простому поиску Мерсенна (GIMPS), и решите проблему за 20 минут.

(много способов решить проблему, но я надеюсь, что это помечено как юмор)

0
10.12.2008 15:17:57