June 3rd, 2007

with Cat The Cat

Про русский язык с точки зрения инстранца.

with Cat The Cat

Сижу, мучаю инженерную задачу.

Все насчет той модели вычислителя будущего.

Судя по всему, я уперся в пропускную способность канала. Тем не менее, догнал загрузку до 10-11%. Одна десятая от недостижимого максимума. ;)

Вычислитель будущего представляет собой stateless message passing system. ;)

Треть сообщений от исполнительного устройства идет наружу. При этом сообщения "закольцованы," то есть, для получения в будущем сообщения Mj в выбранное нами исполнительное устройство P необходимо, чтобы P послало сообщение Mi, i<j. Понятно, что чем дольше идет Mi до назначенного ему ИУ, тем позже сработает Mj.

При этом сообщения конфликтуют друг с другом за канал их передачи. Он у меня толщиной в одно сообщение.

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

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

Еще вот, что я хотел написать.

Давным-давно кое-кто (я помню, кто;) упомянул в моем журнале, что алгоритм решета Эратосфена лучше записывается в императивном стиле.

Вот, примерно, таким образом:
primes[0] = 0;
for (i = 1; i < N;i++)
    primes[i] = 1;
prime = 2;
while (prime < N) {
    /* сбросим все флаги простых чисел для делящихся на prime */
    for (i = prime*2; i < N; i += prime)
        primes[i] = 0;
    /* отыщем новый prime */
    for (i = prime+1; i < N; i++)
        if (primes[i])
            break;
    if (i>=N)
        break; /* не смогли найти */
    prime = i;
}
/* вытащив из primes все ненулевые элементы мы получим список простых, меньше N */
Вроде, не сильно наврал.

Распараллелить его трудно.

Сейчас попытаемся.
primes[0][0] = 0;
for (i = 1; i < N;i++)
    primes[0][i] = 1;
prime = 2;
whileCount = 0;
while (prime < N) {
    whileCount ++; /* whileCount = 1..(нужное знечение),
                      и по выходу из цикла должен содержать индекс текущего результата */
    /* сбросим все флаги простых чисел для делящихся на prime */
    for (i = 0, k = prime*2; i < N; i++) { /* цикл А */
        if (i == k) {
            primes[whileCount][i] = 0;
            k += prime;
        } else
            primes[whileCount][i] = primes[whileCount-1][i]; /* с предыдущей итерации */
    }
    /* отыщем новый prime */
    for (i = prime+1; i < N; i++) /* цикл Б */
        if (primes[whileCount][i])
            break;
    if (i>=N)
        break; /* не смогли найти */
    prime = i;
}
/* вытащив из primes все ненулевые элементы мы получим список простых, меньше N */
В принципе, как только мы дошли в копировании и сбрасывании значений в цикле А до индекса i=prime+1, мы можем в параллель запускать цикл Б. И даже цикл с новым whileCount, если синхронизация достаточно легковесна. И даже со многими whileCount, nes pa?

Посылка сообщений, насколько мне известно, гарантирует такую синхрониацию. Почему и занимаюсь stateless message passing system. ;)

Еще, что интересно, я записал алгоритм в функциональном стиле. ;)

В primes[j][i] запись происходит-то всего один раз. ;)

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

Ну, или там в районе Профсоюзной поставили мощный прожектор. ;)
with Cat The Cat

Продолжение в Ставрополье.