Параллельное программирование

На текущей работе пишем на Reactor. Технология классная, но как всегда есть много НО. Некоторые вещи раздражают, код сложнее писать и читать, с ThreadLocal совсем беда. Решил посмотреть какие проблемы уйдут, если перейти на Kotlin Coroutines, а какие проблемы, наоборот, добавятся.

Карточка пациента

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

В двух словах об алгоритме:

Переводим деньги с одного счёта на другой, записывая транзакции о факте перевода.

Перевод идемпотентен, так что если транзакция уже есть в БД, то отвечаем клиенту, что всё хорошо. При вставке транзакции может вылететь DataIntegrityViolationException, это тоже значит, что транзакция уже есть.

Чтобы не уйти в минус есть проверка в коде + Optimistic lock, который не позволяет конкурентно обновлять счета. Чтобы он работал нужен retry и дополнительная обработка ошибок.

Жалобы пациента

1. Stacktrace не показывает каким образом мы попали в проблемное место.

2. Код явно сложнее, чем был бы на блокирующих технологиях.

3. Многоступенчатая вложенность кода из-за flatMap.

4. Неудобная обработка ошибок и их выброс.

5. Сложная обработка поведения для Mono.empty().

6. Сложности с логированием, если надо в лог добавить что-то глобальное, например traceId. (в статье не описываю, но те же проблемы с другими ThreadLocal переменными, например SpringSecurity)

7. Неудобно дебажить.

8. Неявное api для параллелизации.

Ход лечения

Написал отдельный PR перехода с Java на Kotlin.

Интеграция почти везде гладкая.

Понадобилось добавить com.fasterxml.jackson.module:jackson-module-kotlin чтобы заработала сериализация data классов и org.jetbrains.kotlin.plugin.spring чтобы не прописывать везде open модификаторы.

В контроллере достаточно было написать suspend fun transfer(@RequestBody request: TransferRequest) вместо public Mono<Void> transfer(@RequestBody TransferRequest request)

В репозитории написал suspend fun save(account: Account): Account вместо Mono<Account> save(Account account); Единственное, репозитории не определяются, если в них только suspend функции, надо, чтобы хоть один метод работал с Reactor типами.

Тесты обернул в runBlocking { }, чтобы можно было вызывать suspend функции.

Для реализации Retry использовал библиотеку kotlin-retry. Единственное, в ней не было функции фильтрации по классу ошибки, но это было легко добавить (завёл PR).

Ну и, естественно, переписал алгоритм. Все детали опишу ниже по-отдельности.

Было:

public Mono<Void> transfer(String transactionKey, long fromAccountId,                           long toAccountId, BigDecimal amount) {  return transactionRepository.findByUniqueKey(transactionKey)    .map(Optional::of)    .defaultIfEmpty(Optional.empty())    .flatMap(withMDC(foundTransaction -> {      if (foundTransaction.isPresent()) {        log.warn("retry of transaction " + transactionKey);        return Mono.empty();      }      return accountRepository.findById(fromAccountId)        .switchIfEmpty(Mono.error(new AccountNotFound()))        .flatMap(fromAccount -> accountRepository.findById(toAccountId)          .switchIfEmpty(Mono.error(new AccountNotFound()))          .flatMap(toAccount -> {            var transactionToInsert = Transaction.builder()              .amount(amount)              .fromAccountId(fromAccountId)              .toAccountId(toAccountId)              .uniqueKey(transactionKey)              .build();            var amountAfter = fromAccount.getAmount().subtract(amount);            if (amountAfter.compareTo(BigDecimal.ZERO) < 0) {              return Mono.error(new NotEnoghtMoney());            }            return transactionalOperator.transactional(              transactionRepository.save(transactionToInsert)                .onErrorResume(error -> {                  //transaction was inserted on parallel transaction,                  //we may return success response                  if (error instanceof DataIntegrityViolationException             && error.getMessage().contains("TRANSACTION_UNIQUE_KEY")) {                    return Mono.empty();                  } else {                    return Mono.error(error);                  }                })                .then(accountRepository.transferAmount(                  fromAccount.getId(), fromAccount.getVersion(),                   amount.negate()                ))                .then(accountRepository.transferAmount(                  toAccount.getId(), toAccount.getVersion(), amount                ))            );          }));    }))    .retryWhen(Retry.backoff(3, Duration.ofMillis(1))      .filter(OptimisticLockException.class::isInstance)      .onRetryExhaustedThrow((__, retrySignal) -> retrySignal.failure())    )    .onErrorMap(      OptimisticLockException.class,      e -> new ResponseStatusException(        BANDWIDTH_LIMIT_EXCEEDED,        "limit of OptimisticLockException exceeded", e      )    )    .onErrorResume(withMDC(e -> {      log.error("error on transfer", e);      return Mono.error(e);    }));}

Стало:

suspend fun transfer(transactionKey: String, fromAccountId: Long,                     toAccountId: Long, amount: BigDecimal) {  try {    try {      retry(limitAttempts(3) + filter { it is OptimisticLockException }) {        val foundTransaction = transactionRepository          .findByUniqueKey(transactionKey)        if (foundTransaction != null) {          logger.warn("retry of transaction $transactionKey")          return@retry        }        val fromAccount = accountRepository.findById(fromAccountId)          ?: throw AccountNotFound()        val toAccount = accountRepository.findById(toAccountId)          ?: throw AccountNotFound()        if (fromAccount.amount - amount < BigDecimal.ZERO) {          throw NotEnoghtMoney()        }        val transactionToInsert = Transaction(          amount = amount,          fromAccountId = fromAccountId,          toAccountId = toAccountId,          uniqueKey = transactionKey        )        transactionalOperator.executeAndAwait {          try {            transactionRepository.save(transactionToInsert)          } catch (e: DataIntegrityViolationException) {            if (e.message?.contains("TRANSACTION_UNIQUE_KEY") != true) {              throw e;            }          }          accountRepository.transferAmount(            fromAccount.id!!, fromAccount.version, amount.negate()          )          accountRepository.transferAmount(            toAccount.id!!, toAccount.version, amount          )        }      }    } catch (e: OptimisticLockException) {      throw ResponseStatusException(        BANDWIDTH_LIMIT_EXCEEDED,         "limit of OptimisticLockException exceeded", e      )    }  } catch (e: Exception) {    logger.error(e) { "error on transfer" }    throw e;  }}

Stacktraces

Пожалуй, это самое главное.

Было:

o.s.w.s.ResponseStatusException: 509 BANDWIDTH_LIMIT_EXCEEDED "limit of OptimisticLockException exceeded"; nested exception is c.g.c.v.r.OptimisticLockExceptionat c.g.c.v.r.services.Ledger.lambda$transfer$5(Ledger.java:75)...Caused by: c.g.c.v.r.OptimisticLockException: nullat c.g.c.v.r.repos.AccountRepositoryImpl.lambda$transferAmount$0(AccountRepositoryImpl.java:27)at r.c.p.MonoFlatMap$FlatMapMain.onNext(MonoFlatMap.java:125)  ...

Стало:

error on transfer o.s.w.s.ResponseStatusException: 509 BANDWIDTH_LIMIT_EXCEEDED "limit of OptimisticLockException exceeded"; nested exception is c.g.c.v.r.OptimisticLockExceptionat c.g.c.v.r.services.Ledger.transfer$suspendImpl(Ledger.kt:70)at c.g.c.v.r.services.Ledger$transfer$1.invokeSuspend(Ledger.kt)...Caused by: c.g.c.v.r.OptimisticLockException: nullat c.g.c.v.r.repos.AccountRepositoryImpl.transferAmount(AccountRepositoryImpl.kt:24)...at c.g.c.v.r.services.Ledger$transfer$3$1.invokeSuspend(Ledger.kt:65)at c.g.c.v.r.services.Ledger$transfer$3$1.invoke(Ledger.kt)at o.s.t.r.TransactionalOperatorExtensionsKt$executeAndAwait$2$1.invokeSuspend(TransactionalOperatorExtensions.kt:30)(Coroutine boundary)at o.s.t.r.TransactionalOperatorExtensionsKt.executeAndAwait(TransactionalOperatorExtensions.kt:31)at c.g.c.v.r.services.Ledger$transfer$3.invokeSuspend(Ledger.kt:56)at com.github.michaelbull.retry.RetryKt$retry$3.invokeSuspend(Retry.kt:38)at c.g.c.v.r.services.Ledger.transfer$suspendImpl(Ledger.kt:35)at c.g.c.v.r.controllers.LedgerController$transfer$2$1.invokeSuspend(LedgerController.kt:20)at c.g.c.v.r.controllers.LedgerController$transfer$2.invokeSuspend(LedgerController.kt:19)at kotlin.reflect.full.KCallables.callSuspend(KCallables.kt:55)at o.s.c.CoroutinesUtils$invokeSuspendingFunction$mono$1.invokeSuspend(CoroutinesUtils.kt:64)(Coroutine creation stacktrace)at k.c.i.IntrinsicsKt__IntrinsicsJvmKt.createCoroutineUnintercepted(IntrinsicsJvm.kt:122)at k.c.i.CancellableKt.startCoroutineCancellable(Cancellable.kt:30)...Caused by: c.g.c.v.r.OptimisticLockException: nullat c.g.c.v.r.repos.AccountRepositoryImpl.transferAmount(AccountRepositoryImpl.kt:24)...at c.g.c.v.r.services.Ledger$transfer$3$1.invokeSuspend(Ledger.kt:65)at c.g.c.v.r.services.Ledger$transfer$3$1.invoke(Ledger.kt)at o.s.t.r.TransactionalOperatorExtensionsKt$executeAndAwait$2$1.invokeSuspend(TransactionalOperatorExtensions.kt:30)...

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

В Java очень куцая информация. Да, ошибка есть. Даже видно на какой строчке она вылетела. Только непонятно а как мы в эту строчку кода попали. В Kotlin версии виден весь трейс от контроллера.

Вот представьте себе, что вы видите ошибку в логе где-то на обращении в регулярно вызываемый метод. А кто его вызывал? Придётся по логам рядом искать. Это хорошо, если логи объединены через что-нибудь вроде traceId (thread name нам не поможет) и вообще логи есть.

Сложность кода

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

Многоступенчатая вложенность кода

Никаких flatMap. Добавились вложения из-за явных try catch, но схожая логика вся объявлена на одном уровне.

Было:

return accountRepository.findById(fromAccountId)  .switchIfEmpty(Mono.error(new AccountNotFound()))  .flatMap(fromAccount -> accountRepository.findById(toAccountId)    .switchIfEmpty(Mono.error(new AccountNotFound()))    .flatMap(toAccount -> {      ...    })

Стало:

val fromAccount = accountRepository.findById(fromAccountId)  ?: throw AccountNotFound()val toAccount = accountRepository.findById(toAccountId)  ?: throw AccountNotFound()...

Обработка ошибок и их выброс

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

Было:

return transactionRepository.findByUniqueKey(transactionKey)  ...  .onErrorMap(    OptimisticLockException.class,    e -> new ResponseStatusException(      BANDWIDTH_LIMIT_EXCEEDED,       "limit of OptimisticLockException exceeded", e    )  )

Стало:

try {  val foundTransaction = transactionRepository    .findByUniqueKey(transactionKey)  ...} catch (e: OptimisticLockException) {  throw ResponseStatusException(    BANDWIDTH_LIMIT_EXCEEDED,     "limit of OptimisticLockException exceeded", e  )}

Ошибки выбрасывать можно просто через throw, а не возвращая объект ошибки. В Reactor меня особенно раздражают конструкции вида:

.flatMap(foo -> {  if (foo.isEmpty()) {     return Mono.error(new IllegalStateException());  } else {    return Mono.just(foo);  }})

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

Mono.empty()

Это заслуживает отдельного обсуждения. В реактор нельзя передавать null в качестве результата. При этом нельзя написать C5C.

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

В Kotlin будет not null тип, если ты точно знаешь, что результат будет. Или это будет nullable тип и компилятор обяжет тебя что-то с этим сделать.

Конкретно на нашем примере:

Было:

return transactionRepository.findByUniqueKey(transactionKey)  .map(Optional::of)  .defaultIfEmpty(Optional.empty())  .flatMap(foundTransaction -> {    if (foundTransaction.isPresent()) {      log.warn("retry of transaction " + transactionKey);      return Mono.empty();    }...

Стало:

val foundTransaction = transactionRepository  .findByUniqueKey(transactionKey)if (foundTransaction != null) {  logger.warn("retry of transaction $transactionKey")  return@retry}...

Может, как-то можно эту логику написать адекватнее на Reactor, но то что я нагуглил выглядит ещё хуже.

Логирование и контекст

Допустим, мы хотим всегда логировать traceId во время обработки запроса. ThreadLocal больше не работает, в том числе и MDC (контекст для логирования). Что делать?

Есть контекст. И в Reactor и в Coroutines контекст immutable, так что новое значение в MDC подбрасывать будет не так просто (нужно пересоздавать контекст).

Чтобы работало в Java надо написать фильтр, который сохранит traceId в контекст:

@Componentpublic class TraceIdFilter implements WebFilter {  @Override  public Mono<Void> filter(    ServerWebExchange exchange, WebFilterChain chain  ) {    var traceId = Optional.ofNullable(      exchange.getRequest().getHeaders().get("X-B3-TRACEID")    )      .orElse(Collections.emptyList())      .stream().findAny().orElse(UUID.randomUUID().toString());    return chain.filter(exchange)      .contextWrite(context ->        LoggerHelper.addEntryToMDCContext(context, "traceId", traceId)      );  }}

И каждый раз, когда мы хотим что-то залогировать, надо переносить traceId из контекста в MDC:

public static <T, R> Function<T, Mono<R>> withMDC(  Function<T, Mono<R>> block) {  return value -> Mono.deferContextual(context -> {    Optional<Map<String, String>> mdcContext = context      .getOrEmpty(MDC_ID_KEY);    if (mdcContext.isPresent()) {      try {        MDC.setContextMap(mdcContext.get());        return block.apply(value);      } finally {        MDC.clear();      }    } else {      return block.apply(value);    }  });}

Да, это опять Mono. Т.е. мы можем логировать только тогда, когда код позволяет вернуть Mono. Например вот так:

.onErrorResume(withMDC(e -> {  log.error("error on transfer", e);  return Mono.error(e);}))

В Kotlin проще. Нужно написать фильтр, чтобы сохранить traceId сразу в MDC:

@Componentclass TraceIdFilter : WebFilter {  override fun filter(    exchange: ServerWebExchange, chain: WebFilterChain  ): Mono<Void> {    val traceId = exchange.request.headers["X-B3-TRACEID"]?.first()     MDC.put("traceId", traceId ?: UUID.randomUUID().toString())    return chain.filter(exchange)  }}

И при создании корутины вызывать withContext(MDCContext()) { }

Каждый раз на время работы корутины, будет восстанавливаться MDC и в логах будет traceId. Во время записи в лог ни о чем задумываться не нужно.

Тут есть одно НО, об этом позже.

Дебаг

В Java Reactor проблемы с дебагом примерно те же, что и со стектрейсом: нужно думать о том, кто в каком порядке кого вызвал, ставить breakpoints в лямбдах и т.д..

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

Всё идеально, кроме возможности запускать suspend функции во время дебага. На это уже есть issue. Правда, надо сказать, что и в Java Reactor особо не получается в evaluate сделать то, что хочется.

Параллелизация

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

Было:

return Mono.zip(  transactionRepository.findByUniqueKey(transactionKey)    .map(Optional::of)    .defaultIfEmpty(Optional.empty()),  accountRepository.findById(fromAccountId)    .switchIfEmpty(Mono.error(new AccountNotFound())),  accountRepository.findById(toAccountId)    .switchIfEmpty(Mono.error(new AccountNotFound())),).flatMap(withMDC(fetched -> {  var foundTransaction = fetched.getT1();  var fromAccount = fetched.getT2();  var toAccount = fetched.getT3();  if (foundTransaction.isPresent()) {    log.warn("retry of transaction " + transactionKey);    return Mono.empty();  }  ...}

Стало:

val foundTransactionAsync = GlobalScope.async(coroutineContext) {  logger.info("async fetch of transaction $transactionKey")  transactionRepository.findByUniqueKey(transactionKey)}val fromAccountAsync = GlobalScope.async(coroutineContext) {   accountRepository.findById(fromAccountId) }val toAccountAsync = GlobalScope.async(coroutineContext) {   accountRepository.findById(toAccountId) }if (foundTransactionAsync.await() != null) {  logger.warn("retry of transaction $transactionKey")  return@retry}val fromAccount = fromAccountAsync.await() ?: throw AccountNotFound()val toAccount = toAccountAsync.await() ?: throw AccountNotFound()

В Kotlin версии есть явное указание вот это выполни асинхронно, вместо выполни всё это в параллель в Reactor.

Что самое важное, код ведёт себя по-разному. В случае с Reactor мы создаем три параллельных запроса и продолжаем работу только после того, как все три завершатся. С корутинами мы запускаем все три запроса и ждать чего-то начинаем только при вызове foundTransactionAsync.await(). Таким образом, если transactionRepository.findByUniqueKey() выполнится быстрее, то мы завершим обработку, без ожидания accountRepository.findById() (эти операции отменятся).

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

val foundTransactionAsync = GlobalScope.async(coroutineContext) {  logger.info("async fetch of transaction $transactionKey")  transactionRepository.findByUniqueKey(transactionKey)}val fromAccountAsync = GlobalScope.async(coroutineContext) {  accountRepository.findById(fromAccountId)}val toAccountAsync = GlobalScope.async(coroutineContext) {  accountRepository.findById(toAccountId)}if (foundTransactionAsync.await() != null) {  logger.warn("retry of transaction $transactionKey")  return@retry}val transactionToInsert = Transaction(  amount = amount,  fromAccountId = fromAccountId,  toAccountId = toAccountId,  uniqueKey = transactionKey)transactionalOperator.executeAndAwait {  try {    transactionRepository.save(transactionToInsert)  } catch (e: DataIntegrityViolationException) {    if (e.message?.contains("TRANSACTION_UNIQUE_KEY") != true) {      throw e;    }  }  val fromAccount = fromAccountAsync.await() ?: throw AccountNotFound()  val toAccount = toAccountAsync.await() ?: throw AccountNotFound()  if (fromAccount.amount - amount < BigDecimal.ZERO) {    throw NotEnoghtMoney()  }  accountRepository.transferAmount(    fromAccount.id!!, fromAccount.version, amount.negate()  )  accountRepository.transferAmount(    toAccount.id!!, toAccount.version, amount  )}

Здесь я ожидаю асинхронный запрос уже внутри открытой БД транзакции. Т.е. мы при работе с одним коннектом, ждём результата выполнения на другом коннекте. Так делать не стоит, скорее для примера, хоть оно и работает (пока коннектов хватает).

Побочные эффекты

Конечно, есть проблемы, куда без них.

Надо явно указывать context и scope

Чтобы программа работала как ожидается, надо:

1. Каждому запросу назначить scope. Таким образом все порождаемые при обработке запроса корутины будут отменены все вместе, например, в случае ошибки.

2. В каждом запросе проставить context. Зачем нам нужен контекст я рассказывал в разделе про логирование.

Spring не берет на себя заботу об этом вопросе, приходится в контроллере указывать явно:

@PutMapping("/transfer")suspend fun transfer(@RequestBody request: TransferRequest) {  coroutineScope {    withContext(MDCContext()) {      ledger.transfer(request.transactionKey, request.fromAccountId,                       request.toAccountId, request.amount)    }  }}

Естественно, можно объединить в одну функцию и потом через regexp проверить, что во всех методах есть нужный вызов. Но лучше была бы какая-то автоматизация для этого.

Передача context

В случае, если мы порождаем дополнительные корутины, необходимо явным образом передать текущий контекст. Вот пример:

val foundTransactionAsync = GlobalScope.async(coroutineContext) {  logger.info("async fetch of transaction $transactionKey")  transactionRepository.findByUniqueKey(transactionKey)}

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

AOP и suspend

Автоматизацию, которую я упоминал в первом пункте, написать самому сложно. Потому что пока нельзя нормально написать aspect для suspend функции.

Я в итоге сумел написать такой аспект. Но для объяснения того, как это работает понадобится отдельная статья.

Надеюсь, появится более адекватный способ писать аспекты (попробую этому посодействовать).

Оценка лечения

Все проблемы исчезли. Добавилась пара новых, но оно терпимо.

Надо сказать, что корутины быстро развиваются и я ожидаю только улучшения работы с ними.

Видно, что команда JetBrains внимательно отнеслась к проблемам разработчиков. Насколько я знаю, где-то год назад всё ещё были проблемы с дебагом и стактрейсом, к примеру.

Самое главное, с корутинами не надо в голове держать все особенности работы Reactor и его могучий API. Ты просто пишешь код.

Реактивное программирование один из самых актуальных трендов современности. Обучение ему сложный процесс, особенно если нет подходящих материалов. В качестве своеобразного дайджеста может выступить эта статья. На конференции РИТ++ 2020 эксперт и тренер Luxoft Training Владимир Сонькин рассказал о фишках управления асинхронными потоками данных и подходах к ним, а также показал на примерах, в каких ситуациях нужна реактивность, и что она может дать.

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

Reactivity

Реактивное программирование это асинхронность, соединенная с потоковой обработкой данных. То есть если в асинхронной обработке нет блокировок потоков, но данные обрабатываются все равно порциями, то реактивность добавляет возможность обрабатывать данные потоком. Помните тот пример, когда начальник поручает задачу Васе, тот должен передать результат Диме, а Дима вернуть начальнику? Но у нас задача это некая порция, и пока она не будет сделана, дальше передать ее нельзя. Такой подход действительно разгружает начальника, но Дима и Вася периодически простаивают, ведь Диме надо дождаться результатов работы Васи, а Васе дождаться нового задания.

А теперь представьте, что задачу разбили на множество подзадач. И теперь они плывут непрерывным потоком:

Говорят, когда Генри Форд придумал свой конвейер, он повысил производительность труда в четыре раза, благодаря чему ему удалось сделать автомобили доступными. Здесь мы видим то же самое: у нас небольшие порции данных, а конвейер с потоком данных, и каждый обработчик пропускает через себя эти данные, каким-то образом их преобразовывая. В качестве Васи и Димы у нас выступают потоки выполнения (threads), обеспечивая, таким образом, многопоточную обработку данных.

На этой схеме показаны разные технологии распараллеливания, добавлявшиеся в Java в разных версиях. Как мы видим, спецификация Reactive Streams на вершине она не заменяет всего, что было до нее, но добавляет самый высокий уровень абстракции, а значит ее использование просто и эффективно. Попробуем в этом разобраться.

Идея реактивности построена на паттерне проектирования Observer.

Давайте вспомним, что это за паттерн. У нас есть подписчики и то, на что мы подписываемся. В качестве примера здесь рассмотрен Твиттер, но подписаться на какое-то сообщество или человека, а потом получать обновления можно в любой соцсети. После подписки, как только появляется новое сообщение, всем подписчикам приходит notify, то есть уведомление. Это базовый паттерн.

В данной схеме есть:

• Publisher тот, кто публикует новые сообщения;

• Observer тот, кто на них подписан. В реактивных потоках подписчик обычно называется Subscriber. Термины разные, но по сути это одно и то же. В большинстве сообществ более привычны термины Publisher/Subscriber.

Это базовая идея, на которой все строится.

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

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

Если бы у нас был традиционный, а не реактивный подход, мы бы писали код, который каждые пять минут опрашивает детектор дыма и датчик температуры, и включает или выключает колокольчик. Однако в реактивном подходе за нас это делает реактивный фреймворк, а мы только прописываем условия: колокольчик активен, когда детектор больше X, а температура больше Y. Это происходит каждый раз, когда приходит новое событие.

От детектора дыма идет поток данных: например, значение 10, потом 12, и т.д. Температура тоже меняется, это другой поток данных 20, 25, 15. Каждый раз, когда появляется новое значение, результат пересчитывается, что приводит к включению или выключению системы оповещения. Нам достаточно сформулировать условие, при котором колокольчик должен включиться.

Если вернуться к паттерну Observer, у нас детектор дыма и термометр это публикаторы сообщений, то есть источники данных (Publisher), а колокольчик на них подписан, то есть он Subscriber, или наблюдатель (Observer).

Немного разобравшись с идеей реактивности, давайте углубимся в реактивный подход. Мы поговорим об операторах реактивного программирования. Операторы позволяют каким-либо образом трансформировать потоки данных, меняя данные и создавая новые потоки. Для примера рассмотрим оператор distinctUntilChanged. Он убирает одинаковые значения, идущие друг за другом. Действительно, если значение на детекторе дыма не изменилось зачем нам на него реагировать и что-то там пересчитывать:

Reactive approach

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

Клики здесь это поток щелчков мышкой (на схеме 1, 2, 1, 3). Нам нужно их сгруппировать. Для этого мы используем оператор throttle. Говорим, что если два события (два клика) произошли в течение 250 мс, их нужно сгруппировать. На второй схеме представлены сгруппированные значения (1, 2, 1, 3). Это поток данных, но уже обработанных в данном случае сгрупированных.

Таким образом начальный поток преобразовался в другой. Дальше нужно получить длину списка ( 1, 2, 1, 3). Фильтруем, оставляя только те значения, которые больше или равны 2. На нижней схеме осталось только два элемента (2, 3) это и были двойные клики. Таким образом, мы преобразовали начальный поток в поток двойных кликов.

Это и есть реактивное программирование: есть потоки на входе, каким-то образом мы пропускаем их через обработчики, и получаем поток на выходе. При этом вся обработка происходит асинхронно, то есть никто никого не ждет.

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

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

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

Observable example

Теперь посмотрим на код, в котором мы публикуем события:

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

Девушка (Publisher) опубликовала эти значения, а Observers на них подписываются и печатают значения из потока.

Это похоже на потоки данных (Stream) в Java 8. И тут, и там синхронные потоки. И здесь, и в Java 8 список значений нам известен сразу. Но если бы использовался обычный для Java 8 поток, мы не могли бы туда что-то докладывать. В стрим ничего нельзя добавить: он синхронный. В нашем примере потоки асинхронные, то есть в любой момент времени в них могут появляться новые события скажем, если через год откроется учебный центр в новой локации она может добавиться в поток, и реактивные операторы правильно обработают эту ситуацию. Мы добавили события и сразу же на них подписались:

locations.subscribe(s -> System.out.println(s)))

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

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

Implementing and subscribing to an observer

В Java 9 нет реализации реактивных потоков только спецификация. Но есть несколько библиотек реализаций реактивного подхода. В этом примере используется библиотека RxJava. Мы подписываемся на поток данных, и определяем несколько обработчиков, то есть методы, которые будут запущены в начале обработки потока (onSubscribe), при получении каждого очередного сообщения (onNext), при возникновении ошибки (onError) и при завершении потока (onComplete):

Давайте посмотрим на последнюю строчку.

locations.map(String::length).filter(l -> l >= 5).subscribe(observer);

Мы используем операторы map и filter. Если вы работали со стримами Java 8, вам, конечно, знакомы map и filter. Здесь они работают точно так же. Разница в том, что в реактивном программировании эти значения могут появляться постепенно. Каждый раз, когда приходит новое значение, оно проходит через все преобразования. Так, String::length заменит строчки на длину в каждой из строк.

В данном случае получится 5 (Minsk), 6 (Krakow), 6 (Moscow), 4 (Kiev), 5 (Sofia). Фильтруем, оставляя только те, что больше 5. У нас получится список длин строк, которые больше 5 (Киев отсеется). Подписываемся на итоговый поток, после этого вызывается Observer и реагирует на значения в этом итоговом потоке. При каждом следующем значении он будет выводить длину:

public void onNext(Integer value) {

System.out.println("Length: " + value);

То есть сначала появится Length 5, потом Length 6. Когда наш поток завершится, будет вызван onComplete, а в конце появится надпись "Done.":

public void onComplete() {

System.out.println("Done.");

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

Если где-то произойдет ошибка, мы можем на нее отреагировать:

public void onError(Throwable e) {

e.printStackTrace();

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

Reactive Streams spec

Реактивные потоки вошли в Java 9 как спецификация.

Если предыдущие технологии (Completable Future, Fork/Join framework) получили свою имплементацию в JDK, то реактивные потоки имплементации не имеют. Есть только очень короткая спецификация. Там всего 4 интерфейса:

Если рассматривать наш пример из картинки про Твиттер, мы можем сказать, что:

Publisher девушка, которая постит твиты;

Subscriber подписчик. Он определяет , что делать, если:

• Начали слушать поток (onSubscribe). Когда мы успешно подписались, вызовется эта функция;

• Появилось очередное значение в потоке (onNext);

• Появилось ошибочное значение (onError);

• Поток завершился (onComplete).

Subscription у нас есть подписка, которую можно отменить (cancel) или запросить определенное количество значений (request(long n)). Мы можем определить поведение при каждом следующем значении, а можем забирать значения вручную.

Processor обработчик это два в одном: он одновременно и Subscriber, и Publisher. Он принимает какие-то значения и куда-то их кладет.

Если мы хотим на что-то подписаться, вызываем Subscribe, подписываемся, и потом каждый раз будем получать обновления. Можно запросить их вручную с помощью request. А можно определить поведение при приходе нового сообщения (onNext): что делать, если появилось новое сообщение, что делать, если пришла ошибка и что делать, если Publisher завершил поток. Мы можем определить эти callbacks, или отписаться (cancel).

PUSH / PULL модели

Существует две модели потоков:

• Push-модель когда идет проталкивание значений.

Например, вы подписались на кого-то в Telegram или Instagram и получаете оповещения (они так и называются push-сообщения, вы их не запрашиваете, они приходят сами). Это может быть, например, всплывающее сообщение. Можно определить, как реагировать на каждое новое сообщение.

• Pull-модель когда мы сами делаем запрос.

Например, мы не хотим подписываться, т.к. информации и так слишком много, а хотим сами заходить на сайт и узнавать новости.

Для Push-модели мы определяем callbacks, то есть функции, которые будут вызваны, когда придет очередное сообщение, а для Pull-модели можно воспользоваться методом request, когда мы захотим узнать, что новенького.

Pull-модель очень важна для Backpressure напирания сзади. Что же это такое?

Вы можете быть просто заспамленными своими подписками. В этом случае прочитать их все нереально, и есть шанс потерять действительно важные данные они просто утонут в этом потоке сообщений. Когда подписчик из-за большого потока информации не справляется со всем, что публикует Publisher, получается Backpressure.

В этом случае можно использовать Pull-модель и делать request по одному сообщению, прежде всего из тех потоков данных, которые наиболее важны для вас.

Implementations

Давайте рассмотрим существующие реализации реактивных потоков:

• RxJava. Эта библиотека реализована для разных языков. Помимо RxJava существует Rx для C#, JS, Kotlin, Scala и т.д.

• Reactor Core. Был создан под эгидой Spring, и вошел в Spring 5.

• Akka-стримы от создателя Scala Мартина Одерски. Они создали фреймворк Akka (подход с Actor), а Akka-стримы это реализация реактивных потоков, которые дружат с этим фреймворком.

Во многом эти реализации похожи, и все они реализуют спецификацию реактивных потоков из Java 9.

Посмотрим подробнее на Springовский Reactor.

Function may return

Давайте обобщим, что может возвращать функция:

• Single/Synchronous;

Обычная функция возвращает одно значение, и делает это синхронно.

• Multipple/Synchronous;

Если мы используем Java 8, можем возвращать из функции поток данных Stream. Когда вернулось много значений, их можно отправлять на обработку. Но мы не можем отправить на обработку данные до того, как все они получены ведь Stream работают только синхронно.

• Single/Asynchronous;

Здесь уже используется асинхронный подход, но функция возвращает только одно значение:

• либо CompletableFuture (Java), и через какое-то время приходит асинхронный ответ;

• либо Mono, возвращающая одно значение в библиотеке Spring Reactor.

• Multiple/Asynchronous.

А вот тут как раз реактивные потоки. Они асинхронные, то есть возвращают значение не сразу, а через какое-то время. И именно в этом варианте можно получить поток значений, причем эти значения будут растянуты во времени Таким образом, мы комбинируем преимущества потоков Stream, позволяющих вернуть цепочку значений, и асинхронности, позволяющей отложить возврат значения.

Например, вы читаете файл, а он меняется. В случае Single/Asynchronous вы через какое-то время получаете целиком весь файл. В случае Multiple/Asynchronous вы получаете поток данных из файла, который сразу же можно начинать обрабатывать. То есть можно одновременно читать данные, обрабатывать их, и, возможно, куда-то записывать. . Реактивные асинхронные потоки называются:

• Publisher (в спецификации Java 9);

• Observable (в RxJava);

• Flux (в Spring Reactor).

Netty as a non-blocking server

Рассмотрим пример использования реактивных потоков Flux вместе со Spring Reactor. В основе Reactor лежит сервер Netty. Spring Reactor это основа технологии, которую мы будем использовать. А сама технология называется WebFlux. Чтобы WebFlux работал, нужен асинхронный неблокирующий сервер.

Схема работы сервера Netty похожа на то, как работает Node.js. Есть Selector входной поток, который принимает запросы от клиентов и отправляет их на выполнение в освободившиеся потоки. Если в качестве синхронного сервера (Servlet-контейнера) используется Tomcat, то в качестве асинхронного используется Netty.

Давайте посмотрим, сколько вычислительных ресурсов расходуют Netty и Tomcat на выполнение одного запроса:

Throughput это общее количество обработанных данных. При небольшой нагрузке, до первых 300 пользователей у RxNetty и Tomcat оно одинаковое, а после Netty уходит в приличный отрыв почти в 2 фраза.

Blocking vs Reactive

У нас есть два стека обработки запросов:

• Традиционный блокирующий стек.

• Неблокирующий стек в нем все происходит асинхронно и реактивно.

В блокирующем стеке все строится на Servlet API, в реактивном неблокирующем стеке на Netty.

Сравним реактивный стек и стек Servlet.

В Reactive Stack применяется технология Spring WebFlux. Например, вместо Servlet API используются реактивные стримы.

Чтобы мы получили ощутимое преимущество в производительности, весь стек должен быть реактивным. Поэтому чтение данных тоже должно происходить из реактивного источника.

Например, если у нас используется стандартный JDBC, он является не реактивным блокирующим источником, потому что JDBC не поддерживает неблокирующий ввод/вывод. Когда мы отправляем запрос в базу данных, приходится ждать, пока результат этого запроса придет. Соответственно, получить преимущество не удается.

В Reactive Stack мы получаем преимущество за счет реактивности. Netty работает с пользователем, Reactive Streams Adapters со Spring WebFlux, а в конце находится реактивная база: то есть весь стек получается реактивным. Давайте посмотрим на него на схеме:

Data Repo репозиторий, где хранятся данные. В случае, если есть запросы, допустим, от клиента или внешнего сервера, они через Flux поступают в контроллер, обрабатываются, добавляются в репозиторий, а потом ответ идет в обратную сторону.

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

Операторы

В реактивных потоках огромное количество операторов. Многие из них похожи на те, которые есть в обычных стримах Java. Мы рассмотрим только несколько самых распространенных операторов, которые понадобятся нам для практического примера применения реактивности.

Filter operator

Скорее всего, вы уже знакомы с фильтрами из интерфейса Stream.

По синтаксису этот фильтр точно такой же, как обычный. Но если в стриме Java 8 все данные есть сразу, здесь они могут появляться постепенно. Стрелки вправо это временная шкала, а в кружочках находятся появляющиеся данные. Мы видим, что фильтр оставляет в итоговом потоке только значения, превышающие 10.

Take 2 означает, что нужно взять только первые два значения.

Map operator

Оператор Map тоже хорошо знаком:

Это действие, происходящее с каждым значением. Здесь умножить на десять: было 3, стало 30; было 2, стало 20 и т.д.

Delay operator

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

Reduce operator

Еще один всем известный оператор:

Он дожидается конца работы потока (onComplete) на схеме она представлена вертикальной чертой. После чего мы получаем результат здесь это число 15. Оператор reduce сложил все значения, которые были в потоке.

Scan operator

Этот оператор отличается от предыдущего тем, что не дожидается конца работы потока.

Оператор scan рассчитывает текущее значение нарастающим итогом: сначала был 1, потом прибавил к предыдущему значению 2, стало 3, потом прибавил 3, стало 6, еще 4, стало 10 и т.д. На выходе получили 15. Дальше мы видим вертикальную черту onComplete. Но, может быть, его никогда не произойдет: некоторые потоки не завершаются. Например, у термометра или датчика дыма нет завершения, но scan поможет рассчитать текущее суммарное значение, а при некоторой комбинации операторов текущее среднее значение всех данных в потоке.

Merge operator

Объединяет значения двух потоков.

Например, есть два температурных датчика в разных местах, а нам нужно обрабатывать их единообразно, в общем потоке .

Combine latest

Получив новое значение, комбинирует его с последним значением из предыдущего потока.

Если в потоке возникает новое событие, мы его комбинируем с последним полученным значением из другого потока. Скажем, таким образом мы можем комбинировать значения от датчика дыма и термометра: при появлении нового значения температуры в потоке temperatureStream оно будет комбинироваться с последним полученным значением задымленности из smokeStream. И мы будем получать пару значений. А уже по этой паре можно выполнить итоговый расчет:

temperatureStream.combineLatest(smokeStream).map((x, y) -> x > X && y > Y)

В итоге на выходе у нас получается поток значений true или false включить или выключить колокольчик. Он будет пересчитываться каждый раз, когда будет появляться новое значение в temperatureStream или в smokeStream.

FlatMap operator

Этот оператор вам, скорее всего, знаком по стримам Java 8. Элементами потока в данном случае являются другие потоки. Получается поток потоков. Работать с ними неудобно, и в этих случаях нам может понадобиться уплостить поток.

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

Flatmap часто используется при обработке потока данных, полученных с сервера. Т.к. сервер возвращает поток, чтобы мы смогли обрабатывать отдельные данные, этот поток сначала надо развернуть. Это и делает flatMap.

Buffer operator

Это оператор, который помогает группировать данные. На выходе Buffer получается поток, элементами которого являются списки (List в Java). Он может пригодиться, когда мы хотим отправлять данные не по одному, а порциями.

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

На схеме выше мы группируем отдельные значения по три элемента (так как всего их было пять, получилась коробка из трех, а потом из двух значений). То есть если flatMap распаковывает данные из коробок, buffer, наоборот, упаковывает их.

Всего существует более сотни операторов реактивного программирования. Здесь разобрана только небольшая часть.

Итого

Есть два подхода:

• Spring MVC традиционная модель, в которой используется JDBC, императивная логика и т.д.

• Spring WebFlux, в котором используется реактивный подход и сервер Netty.

Есть кое-что, что их объединяет. Tomcat, Jetty, Undertow могут работать и со Spring MVC, и со Spring WebFlux. Однако дефолтным сервером в Spring для работы с реактивным подходом является именно Netty.

Конференция HighLoad++ 2020 пройдет 20 и 21 мая 2021 года.Приобрести билетыможно уже сейчас.

А совсем скоро состоится еще одно интересное событие, на сей раз онлайн: 18 марта в 17:00 МСК пройдет митап Как устроена самая современная платежная система в МИРе: архитектура и безопасность.

Вместе с разработчиками Mир Plat.Form будем разбираться, как обеспечить устойчивость работы всех сервисов уже на этапе проектирования и как сделать так, чтобы система могла развиваться, не затрагивая бизнес-процессы. Митап будет интересен разработчикам, архитекторам и специалистам по безопасности.

Хотите бесплатно получить материалы конференции мини-конференции Saint HighLoad++ 2020?Подписывайтесьна нашу рассылку.

Специально к старту нового потока курса Fullstack-разработчик на Python, представляем небольшой авторский обзор кроссплатформенного инструмента визуализации многопоточных программ VizTracer. У VizTracer 57 форков и 841 звезд на Github. Настраиваемые события, отчёты в HTML, детальная информация о функциях с их исходным кодом, простота применения, отсутствие зависимостей и малый оверхед превращают VizTracer в мастхэв Python-разработчика.

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

В Python вариантов конкурентности много. Самый распространённый, вероятно, многопоточность, которой добиваются с помощью модуля threading и несколько процессов с помощью модулей myltiprocessing и subprocess, а также недавно появившийся способ async из модуля asyncio. До появления VizTracer в инструментах, использующих эти техники в целях анализа программ, был пробел.

VizTracer инструмент отслеживания и визуализации написанных на Python программ, который помогает логировать, отлаживать и профилировать код. Хотя он хорошо работает в однопоточных программах с одной задачей, польза от него в смысле конкурентных программ делает инструмент уникальным.

Попробуем с простой задачей

Определим, являются ли числа в массиве простыми, и вернём массив логических значений. Вот простое решение:

def is_prime(n):    for i in range(2, n):        if n % i == 0:            return False    return Truedef get_prime_arr(arr):    return [is_prime(elem) for elem in arr]

Выполним его нормально, в один поток, и задействуем VizTracer.

if __name__ == "__main__":    num_arr = [random.randint(100, 10000) for _ in range(6000)]    get_prime_arr(num_arr)

Выполняем команду:

viz_tracer my_program.py

Отчёт стека вызовов показывает, что выполнение кода заняло 140 мс, а большую часть времени заняло выполнение get_prime_arr.

Здесь на каждом элементе массива выполняется функция is_prime. Это ожидаемо и не интересно, если VizTracer вам знаком.

Теперь попробуем многопоточную программу

Сделаем то же самое в программе с несколькими потоками:

if __name__ == "__main__":    num_arr = [random.randint(100, 10000) for i in range(2000)]    thread1 = Thread(target=get_prime_arr, args=(num_arr,))    thread2 = Thread(target=get_prime_arr, args=(num_arr,))    thread3 = Thread(target=get_prime_arr, args=(num_arr,))    thread1.start()    thread2.start()    thread3.start()    thread1.join()    thread2.join()    thread3.join()

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

Если вы знакомы с Python Global Lock (GIL), то можете ожидать, что программа не станет быстрее: из-за оверхеда она выполняется немного дольше 140 мс, однако можно наблюдать конкурентность множества потоков:

Когда работал один поток (и много раз выполнял функции is_prime), другой поток был заморожен (одна функция is_prime). Позже они поменялись. Это произошло из-за GIL, и причина в том, что в Python нет настоящей многопоточности. Возможна конкурентность, но не параллелизм.

Попробуем поработать с multiprocessing

Чтобы достичь параллелизма, воспользуемся библиотекой multiprocessing. Вот новая версия кода с применением этой библиотеки:

if __name__ == "__main__":    num_arr = [random.randint(100, 10000) for _ in range(2000)]       p1 = Process(target=get_prime_arr, args=(num_arr,))    p2 = Process(target=get_prime_arr, args=(num_arr,))    p3 = Process(target=get_prime_arr, args=(num_arr,))    p1.start()    p2.start()    p3.start()    p1.join()    p2.join()    p3.join()

Чтобы запустить его с помощью VizTracer, понадобится дополнительный аргумент:

viztracer --log_multiprocess my_program.py

Вся программа занимает чуть больше 50 мс, задача завершается менее чем за те же 50 мс, то есть программа ускорилась приблизительно втрое. Чтобы сравнить производительность, напишем версию в несколько процессов:

Без GIL множество процессов достигают параллелизма, то есть множество функций is_prime выполняются параллельно.

Однако многопоточность в Python не бесполезна. Например, для вычислительно-интенсивных программ и программ с интенсивным вводом-выводом, при помощи sleep можно имитировать задержку ввода-вывода:

def io_task():    time.sleep(0.01)

Попробуем в однопоточной программе с одной задачей:

if __name__ == "__main__":    for _ in range(3):        io_task()

.

Вся программа занимает 30 мс; ничего особенного. Теперь воспользуемся многопоточностью:

if __name__ == "__main__":    thread1 = Thread(target=io_task)    thread2 = Thread(target=io_task)    thread3 = Thread(target=io_task)    thread1.start()    thread2.start()    thread3.start()    thread1.join()    thread2.join()    thread3.join()

Выполнение занимает 10 мс: ясно, что все потоки работали одновременно и повысили производительность.

Теперь поработаем с asyncio

В Python попробовали ввести интересную функциональность асинхронное программирование. Нашу задачу можно написать асинхронно:

import asyncioasync def io_task():    await asyncio.sleep(0.01)async def main():    t1 = asyncio.create_task(io_task())    t2 = asyncio.create_task(io_task())    t3 = asyncio.create_task(io_task())    await t1    await t2    await t3if __name__ == "__main__":    asyncio.run(main())

Поскольку asyncio буквально однопоточный планировщик с задачами, вы можете использовать VizTracer вместе с этим планировщиком:

Всё те же 10 мс, но большинство отображаемых функций нижележащая структура, которая, вероятно, не интересует пользователей. Чтобы решить эту проблему, можно использовать --log_async флаг разделит задачу на части:

viztracer --log_async my_program.py

Теперь задачи пользователя намного яснее. Большую часть времени выполняемых задач нет: единственное, что делает программа, спит. Вот интересная часть:

На временной шкале показывается, когда задачи создавались и выполнялись. Task-1 была сопрограммой mail(), которая создаёт другие задачи. Задачи 2, 3 и 4 выполняли io_task и sleep, а потом ждали пробуждения. Как показывает график, задачи не перекрывают друг друга, поскольку программа однопоточная, и VizTracer визуализировал её так, чтобы она была понятной. Чтобы сделать код интереснее, добавим вызов time.sleep, чтобы заблокировать асинхронный цикл:

async def io_task():    time.sleep(0.01)    await asyncio.sleep(0.01)

Программа заняла намного больше времени (40 мс) и задачи заняли свои места в асинхронном планировщике. Это поведение очень полезно для диагностики проблем поведения и производительности в асинхронных программах.

Смотрите на происходящее с помощью VizTracer

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

Исходный код VizTracer открыт под лицензией Apache 2.0, поддерживаются все операционные системы Linux , MacOS, Windows. Вы можете узнать больше о его функциях и увидеть исходный код в репозитории VizTracer на Github. А освоить разработку на Python и стать Fullstack-разработчиком на нашем специализированном курсе.

Узнайте, как прокачаться в других специальностях или освоить их с нуля:

• Профессия Data Scientist

• Профессия Data Analyst

• Курс по Data Engineering

Как при распараллеливании кода не мучиться из-за блокировок? На Хабре уже писали о транзакционной памяти, но когда о ней говорит Морис Херлихи, это особый случай. В 1993-м и Хабра никакого не было, и многоядерные процессоры ещё не заявили о себе а Морис уже стал соавтором основополагающей работы о транзакционной памяти. Так что он главный в мире авторитет по этому вопросу, и если вам нужно введение в тему, логично слушать его.

В прошлом году на нашей конференции Hydra он выступил с докладом для широкой публики, где всё начинается с самых азов и затем доходит до менее очевидных вещей. Сейчас мы ждём его на Hydra 2021 с новым докладом а в ожидании этого решили сделать для Хабра текстовый перевод прошлогоднего выступления на русский (видеозапись тоже прилагаем). Далее повествование будет от лица спикера.

Содержание

• Закон Мура

• Закон Амдала

• Варианты блокировок

• Проблемы блокировок

• Транзакционный манифест

• Транзакции против блокировок

• Аппаратная транзакционная память

• Использование транзакционной памяти

• Гибридная транзакционная память

• Открытые для исследования вопросы

Закон Мура

Все знают, что невозможно выступить с докладом по computer science, не упомянув закон Мура хотя бы один раз. Поэтому я отделаюсь от этой обязанности на первом же слайде.

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

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

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

Когда-то давно всё компьютерах всё было просто: одноядерный CPU и память (такая система называется uniprocessor). Сейчас таких архитектур практически не осталось, потому что стало выгоднее использовать множество процессоров в микросхему.

После изобретения многопоточности появились многопроцессорные системы с разделяемой памятью (shared-memory multiprocessor):

Сейчас это тоже вымирающий вид.

А сегодня популярны многоядерные процессоры, иногда их называют CMP (chip multiprocessor). И это означает, что кэш процессора (по крайней мере, часть памяти, коммуникационная среда), размещается целиком на одном кусочке кремния (кристалла).

Так в реальности выглядит довольно небольшой старомодный многоядерный процессор:

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

И это имеет значение для софта, что важно для нас, поскольку доклад не столько о железе, сколько о программировании.

В стародавние времена, когда некоторые из вас ещё и не родились, софт получал ускорение на халяву. Можно было не менять код, а ваш однопроцессорный компьютер начинал работать всё быстрее:

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

В идеальном мире каждый год и ваша программа, и компьютеры становились бы всё более многопоточными, и ваш код продолжал бы так же ускоряться:

Но, конечно, жизнь не так проста.

В реальности так не происходит по ряду причин. И на самом деле всё выглядит примерно так:

Мы пишем программы, делаем их параллельными и многопоточными, добавляем потоки (threads), блокировки (locks), синхронизацию. И хотя железо выглядит всё более мощным и параллельным, ПО не может за ним поспеть. Блокировки вызывают борьбу за ресурсы и разные другие проблемы.

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

Закон Амдала

После закона Мура был закон Амдала, указывающий, как думать о параллелизме. Конечно, этот закон идеализация и абстракция, он не учитывает много нюансов, поэтому не стоит воспринимать его слишком буквально. Но он подсказывает, как подходить к масштабированию ПО путём увеличения параллелизма.

Определим ускорение программы от параллелизма как соотношение количества времени, которое потребуется для её исполнения на одном процессоре, и времени, за которое та же самая программа будет выполняться на n-поточной машине:

При увеличении n нам хотелось бы, чтобы скорость исполнения становилась как можно выше, и нам важно, во сколько раз всё ускорилось.

В итоге закон Амдала выглядит так:

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

А если p равно 1, то код полностью параллельный. И сколько ядер будет, во столько раз он и ускорится.

Но это крайние случаи, а в большинстве интересующих нас приложений p находится где-то между 0 и 1.

Давайте посмотрим, что говорит нам это уравнение. Когда мы берём параллелизируемую часть программы p и делим на количество потоков n, это время выполнения этой части. А 1 p это та последовательная часть, которая не может быть ускорена.

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

Если отвлечься от математики, моё любимое объяснение значимости закона Амдала выглядит так:

На практике закон Амдала гласит, что небольшой фрагмент плохой синхронизации сломает всё. Если вы хотите использовать современное многоядерное аппаратное обеспечение, вам нужно очень хорошо подумать над синхронизацией, потому что именно она контролирует, насколько хорошо ваше приложение будет масштабироваться в современном мире.

Пример

Представим, что вы покупаете 10-ядерную машину. А ваше приложение на 60% параллельное и на 40% последовательное. Иными словами, 60% вашего приложения могут быть распределены между разными ядрами, а 40% приходятся на части, которые нельзя так ускорить скажем, на UI и обращение к диску.

Когда вы сказали начальнику, что хотите купить 10-ядерный компьютер, он сказал: Надеюсь, мы получим десятикратное ускорение нашего приложения. Насколько это возможно с 60% параллельности и 40% последовательности? Какое ускорение вы получите по закону Амдала?

Ответ: вы получите ускорение в 2.17 раз. Итак, у вас стало 10 процессоров, но ускорилось всё только в два раза. Как-то не очень воодушевляет. Поэтому вы попросили своих программистов задерживаться после работы и работать без выходных, чтобы сократить последовательную часть и увеличить многопоточную.

Была проделана большая работа, и в программе стало 80% многопоточности. Вы запускаете программу, чтобы посмотреть, насколько вы приблизились к десятикратному ускорению. И теперь это 3,57. Итак, вы очень усердно работали, ваш код многопоточен на 80%, но вы получили ускорение всего лишь в 3,5 раза. Опять же, мы живём в очень суровом мире.

Вы снова принимаетесь за работу, работаете ещё усерднее и добиваетесь 90% многопоточности в своём коде. И получаете ускорение в 5,26 раза. То есть у вас 10 процессоров, но вы получаете эффект, как от пяти.

Если вы хотите получить ускорение, которое хоть немного похоже на рост числа процессоров у вашего железа, понадобится сделать своё приложение на 99% параллельным и на 1% последовательным. Так вы ускоритесь в 9.17 раз и приблизитесь-таки к десятикратному ускорению.

То есть закон Амдала гласит, что вы не можете просто написать код старым добрым способом, а потом ожидать улучшений от железа. Если ваш код слишком последовательный, то не важно, насколько усердно будут работать инженеры Intel и остальные, потому что вы не сможете в полной мере воспользоваться результатами их труда.

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

Очевидная аналогия шарикоподшипники в велосипеде. Вы можете пойти и купить итальянский гоночный велосипед со сложными деталями, но самая важная из них шарикоподшипники, то есть места, где детали должны двигаться вместе. И многопоточность это такие шарикоподшипники ПО: если эта часть сделана плохо, то всё остальное не особенно имеет значение.

Варианты блокировок

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

Грубая блокировка (coarse-grained locking)

Грубая блокировка это установка одной блокировки сразу на всю структуру данных. Преимущество в том, что это относительно легко сделать правильно. Если вы поставите одну большую блокировку на всю свою систему файлов, на всю базу данных, то сведёте проблему к последовательному программированию. И хотя последовательное программирование тоже непростое, мы хотя бы знаем, как оно делается.

Однако у него очень плохая производительность.

Если у вас когда-либо были в доме маленькие дети, вы знаете, что рано или поздно они доберутся до уборной и закроют там сами себя, и потребуется много времени, чтобы вызволить их оттуда.

Возникает вопрос: Если у нас сложная структура данных, почему бы не блокировать только те её части, которые нужны в текущий момент?

Мелкоструктурная блокировка (fine-grained locking)

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

Однако здесь свой недостаток: бывает сложно написать структуру данных, используя мелкоструктурную блокировку. Можно писать целые исследования о том, как это делать. А если о чём-то можно писать исследования, значит, это не самая удачная инженерная техника!

Помимо этого, у блокировок в целом есть и другие проблемы.

Проблемы блокировок

Блокировки не отказоустойчивы

Если в одном потоке была установлена блокировка, а затем произошёл отказ, то блокировка останется, и никто больше не сможет воспользоваться структурой данных.

С этим можно бороться. Люди разработали очень сложные и изощрённые способы сказать: На случай, если вы устанавливаете блокировку и не снимаете её, есть аварийный способ очистки. Но эти штуки обычно не очень хорошо работают, они сложные и медленные.

Если поток, поставивший блокировку, задерживается, то застопорится и всё остальное. Так что эти подходы крайне ненадёжны.

Блокировки конвенциональны

Есть ещё одна проблема с блокировками, о которой не очень много говорят, но я считаю её очень серьёзной. Дело в том, что блокировки опираются на конвенции, договорённости. По большей части программисты вынуждены следовать протоколам и конвенциям, приходя к соглашениям, чтобы корректно использовать блокировки. Пример такой конвенции отношение между данными блокировки и данными объекта. Блокировка это просто бит или байт в памяти, а объект может быть сложной структурой данных в виде связанного списка или частью сложной структуры данных. Отношение между ними существует только в голове у программиста.

В языках программирования появилось множество механизмов для связывания блокировок с объектами: обработчики событий и другие. Но они никогда не были очень удачными для очень сложных блокировок. В качестве наглядного примера комментарий из ядра Linux:

When a locked buffer is visible to the I/O layer BH_Launder is set. This means before unlocking we must clear BH_Launder,mb() on alpha and then clear BH_Lock, so no reader can see BH_Launder set on an unlocked buffer and then risk to deadlock.

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

Блокировки усложняют простые задачи

Эту проблему трудно определить формально, но при встрече с ней сразу всё понимаешь.

Приведу пример простой задачи, которую сможет понять и старшеклассник. Допустим, у нас есть двухсторонняя очередь (double-ended queue): элементы можно добавлять и убирать с обеих сторон. Поэтому один поток может добавлять элемент с одной стороны, в то время как другой добавляет с противоположной. Ваша задача обеспечить здесь синхронизацию на основе блокировки (lock-based synchronization).

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

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

Если у вас возникнет идея нового подхода к ней, вероятно, результаты можно будет представить на академической конференции. Потому что, насколько мне известно, первое техническое решение этой задачи было опубликовано Магедом Майклом и Майклом Скоттом на конференции PODC в 1996 году. И мне кажется, у дисциплины есть проблема, когда такая простая задача на самом деле так сложна, что её решение достойно публикации.

Наши друзья математики обожают подобные вещи. Среди них много теоретиков, которые выдвигают довольно простые гипотезы, которые потом веками пытаются доказать. Но дисциплина computer science должна быть инженерной: мы должны решать задачи, а не превозносить нерешённые.

Блокировки не компонуются

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

С блокировками ситуация гораздо хуже. Вот, например, у меня есть поток, который хочет переместить что-то из одной очереди в другую:

Я должен убедиться в том, что это перемещение атомарное, то есть никакой другой поток не видит две копии перемещаемого элемента или пропущенный элемент. Каждый наблюдатель видит, что элемент находится либо в одной, либо в другой очереди. Как нам это сделать с блокировкой?

Очевидный способ это сделать: заблокировать очередь-источник, потом заблокировать очередь-адресат, совершить перемещение и затем снять блокировку. Так работает, например, двухфазная блокировка в базах данных.

Но давайте подумаем, каковы последствия такого решения для структуры ПО.

Методы постановки в очередь и удаления из очереди не могут обеспечить внутреннюю синхронизацию. Вы не сможете в Java сделать это synchronized-методом, потому что метод поставит блокировку, произведёт операцию и снимет блокировку, но единственный способ осуществить атомарное перемещение это удерживать блокировку, пока производится перемещение.

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

Но это значит, что вы должны доверять вашим клиентам разрабатывать протоколы и следовать им. Если вы делаете синхронизацию внутри своего метода, тогда вы можете гарантировать, что ваш метод корректен. Но если вы говорите: Вот очередь, которая работает корректно, только если ваши клиенты следуют протоколу, то это очень нехорошая ситуация с точки зрения программной инженерии. Она означает, что вы должны доверять всем, а если кто-то поведёт себя неправильно, то даже если вы всё сделали правильно, можете пострадать.

Паттерн Monitor wait and signal не компонуется

Ещё одна распространённая проблема связана с паттерном Monitor wait and signal. У нас есть поток, который ожидает задание, например, от буфера сообщений. Буфер пуст, так что процесс говорит: Мне нет смысла тратить ресурсы, когда делать нечего. Я буду спать, а ты сообщи мне, когда что-нибудь появится. Когда в буфере появляется элемент, мы можем разбудить поток, и он начнёт потреблять данные.

Меня беспокоит, что этот паттерн не компонуется.

Представим, что поток готов ждать, когда что-нибудь появится в одном из двух буферов. Он говорит: Хорошо, первый буфер пуст, я проверю второй буфер. Второй тоже пуст, так что я засну и буду ждать сигнала от одного из буферов.

Проблема в том, что это невозможно написать, используя классические мониторы. Если вы используете класс Java, то если уж вы установили монитор блокировки, вы видите, что буфер пуст, вы должны заснуть внутри монитора, вы не можете уснуть в одном мониторе и при этом быть активным в другом мониторе. Так что даже очень простые формы компоновки не работают в классических конструкциях синхронизации.

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

Транзакционный манифест

Многие современные практики программирования не подходят для многоядерного мира. Поэтому я предлагаю альтернативу, сосредоточенную на атомарных транзакциях.

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

Общий план таков:

• Заменим блокировки на атомарные транзакции

• Поговорим о разработке языков и библиотек

• Внедрим эффективные реализации

Но в этом докладе мне не хватит времени на все эти темы. Придётся сконцентрироваться на более узкой повестке:

• Транзакции против блокировок

• Аппаратная транзакционная память

• Использование транзакционной памяти

• Объединение транзакций с блокировками

• Открытые для исследования вопросы

Транзакции против блокировок

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

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

Зачастую транзакции производятся спекулятивно. Это означает, что вносится некоторое количество пробных изменений. Эти изменения не являются постоянными. Если мы хотим сделать сделать их постоянными, то говорим об этом, и они коммитятся. То есть мы вносим пробные изменения, и если всё хорошо, то применяем транзакцию. Коммит означает, что мы делаем результат транзакции видимым миру.

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

Атомарные блоки

Перед нами обычный пример атомарного блока:

atomic {    x.remove(3);    y.add(3);}atomic {    y = null;}

Представьте, что у нас есть два потока, один удаляет 3 из x и добавляет 3 к y. Скажем, что мы изобрели ключевое слово atomic, и код с ним исполняется атомарно. Тогда здесь у нас простой пример того, как переместить что-то из одного контейнера в другой. Это один из тех примеров, которые, оказывается, сложно реализовать чисто с использованием блокировок.

Ещё здесь у нас есть параллельный поток, который по сути устанавливает y равным нулю.

Если бы это были обычные несинхронизированные блоки, тогда параллельный доступ к y считался бы гонкой данных. Если бы вы сделали это на C++ без синхронизации, результат вашей программы был бы не определён. На Java же атомарные блоки будут синхронизированы, и результат будет определён. Так что можно считать, что атомарные блоки относятся к синхронизированным блокам.

Двухсторонняя очередь

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

Первый шаг это написать последовательный код.

public void LeftEnq(item x) {    Qnode q = new Qnode(x);    q.left = left;    left.right = q;    left = q;}

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

Второй шаг заключить этот код в атомарный блок:

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

Предупреждение

Но не всё так просто. Не всегда получается установить атомарные блоки вокруг последовательного кода так, чтобы это всегда срабатывало. Это получается лишь в части случаев. Есть множество проблем:

• Ожидание условия (conditional wait). Помните наш поток, который был заблокирован, заглянул в буфер и сказал: Здесь ничего нет, я снимаю блокировку? Требуется объяснить, как это будет работать с транзакциями.

• Могут быть проблемы с ложными конфликтами. Система исполнения транзакций может усматривать конфликт между двумя операциями, когда его на самом деле нет.

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

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

Компоновка?

Помните наш пример с компоновкой, где мы хотели совершить атомарное перемещение элемента из одной очереди в другую?

Опять же, если использовать идеализированную форму транзакций, то это очень просто:

public void Transfer(Queue<T> q1, q2){  atomic {    T x = q1.deq();    q2.enq(x);  }}

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

Ожидание условия

Эта конструкция на самом деле используется в многопоточной версии Haskell, в которой есть встроенные транзакции. Идея в том, что я хочу выполнить удаление из очереди, но если нечего удалять, то пойду спать.

public T LeftDeq() {  atomic {    if (left == null)      retry;      }}

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

То есть здесь тот же результат, что и signal and wait в мониторе, но это гораздо проще использовать и, я думаю, это более понятно интуитивно. Ожидание монитора таит множество опасностей и ловушек, а retry поможет их избегать.

Компонируемое ожидание условие

Если вы хотите скомпоновать условное ожидание, можно ввести конструкцию orElse.

atomic {  x = q1.deq();} orElse {  x = q2.deq();}

Сначала я запущу свой первый метод qt.deq(), если там будет retry, он вернётся и скажет: Извините, я ничего не могу здесь сделать. Тогда вы можете вернуться и попробовать второй, q2.deq(). Если у обоих будет retry, тогда retry будет у всей конструкции она засыпает, откатывает свои результаты, ждёт изменений и затем заново запускает код. То есть снаружи это выглядит так, будто каждый раз, когда вы делаете удаление из очереди, там что-то есть.

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

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

Аппаратная транзакционная память

Пойдём снизу, с железа. Как программисты вы, наверное, не слишком интересуетесь аппаратным обеспечением. Но параллельное программирование пока остаётся довольно незрелой областью, и вы не сможете писать эффективные программы, пока не поймёте кое-что о работе железа.

Есть два вида процессоров, которые поддерживают транзакционную память. В основном я буду говорить об Intel там, начиная с Haswell, используются расширения TSX (Transactional Synchronization Extensions). Есть и другой вид аппаратного обеспечения транзакционной памяти в семействе процессоров Power. Intel больше ориентирован на мелкоструктурную параллельность, а Power на численные вычисления.

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

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

Стандартная когерентность кэша

Стандартная когерентность кэша работает следующим образом. У нас есть набор процессоров, оперативная память, общая шина, которая используется для коммуникации, и есть кэши этих процессоров.

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

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

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

Аппаратная транзакционная память

Аппаратная транзакционная память работает почти по такому же принципу. Один процессор начинает считывать данные и помечает их в кэше: Я считал это от имени транзакции.

Другой процессор также помечает их как транзакционные, теперь у обоих они так помечены.

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

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

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

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

Использование транзакционной памяти

Пояснение о железе потребовалось, потому что оно объясняет некоторые странные вещи, которые происходят, когда вы пишете программы. Как я уже говорил, в процессорах Blue Gene/Q, в System Z и Power8 есть форма транзакционной памяти. Сейчас я буду говорить об Intel, потому что у меня есть время поговорить только о чём-то одном.

На TSX Intel вот так вы пишете транзакцию:

if (_xbegin() == _XBEGIN_STARTED) {  speculative code  _xend()} else {  abort handler}

Это код на C. Вы начинаете с того, что говорите, _xbegin() это системный вызов, который говорит: Я хочу начать спекулятивную транзакцию. Это немного похоже на fork() или vfork() в Unix, он возвращает код. И если вы видите в коде _XBEGIN_STARTED), это значит, что вы внутри транзакции. Если это происходит, вы выполняете свой спекулятивный код.

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

Код обычно выглядит примерно так:

if (_xbegin() == _XBEGIN_STARTED) {  speculative code} else if (status & _XABORT_EXPLICIT) {  aborted by user code} else if (status & _XABORT_CONFLICT) {  read-write conflict} else if (status & _XABORT_CAPACITY) {  cache overflow} else {  }

Какие варианты тут есть?

_XABORT_EXPLICIT: я могу вызвать _xabort(). Мне что-то не понравилось, так что я решил прервать свою транзакцию и откатиться обратно, например, некоторое ожидание условия.

_XABORT-CONFLICT: может быть, у меня с кем-то конфликт синхронизации, если такое происходит, возможно, мне стоит попробовать снова позже.

_XABORT_CAPACITY: Может быть, мой буфер переполнился, я упёрся в некий аппаратный лимит, так что, возможно, пробовать снова не лучшая идея, потому что результат будет тот же, если такое происходит.

И есть ещё много разных кодов прерывания.

Что может пойти не так, если вы используете эти механизмы в написании программы?

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

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

• Транзакция просто не в настроении. Существует множество других причин прерывания транзакции: промах TLB, исполнение неразрешённой команды, отказ страницы. Это происходит крайне редко, но это может произойти.

Так что обычно для использования аппаратной транзакционной памяти разновидности Intel применяется гибридный подход.

Гибридная транзакционная память

Здесь мы объединим транзакционный подход с блокировками. Вот пример такой комбинации.

if (_xbegin() == _XBEGIN_STARTED) {  read lock state  if (lock taken) _xabort();  work;  _xend()} else {  lock->lock();  work;  lock->unlock();}

Идея следующая: я начинаю транзакцию, у меня будет блокировка, я прочитаю её состояние (read lock state). И как только я прочитаю его, это гарантирует, что если другой поток блокирует что-то, это прервёт мою транзакцию (if (lock taken) _xabort();).

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

Пропуск блокировки

Есть паттерн пропуск блокировки (Lock Elision), который поддерживается на аппаратном обеспечении Intel.

<HLF acquire prefix> lock();do work;<HLE release prefix> unlock()

Вы устанавливаете блокировку и отправляете специальный код. В первый раз всё, что вы делаете внутри критической секции, делается спекулятивно с использованием механизма аппаратной транзакционной памяти. Если происходит сбой, то вы повторяете уже с установкой блокировки.

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

Телепортация блокировки

Есть забавное использование транзакционной памяти, которую я называю lock teleportation.

Идея тут в следующем. Есть такой общий паттерн в структурах данных, который называется передающаяся блокировка (hand-over-hand locking). Представьте, я иду вниз по списку, поочередёно устанавливая и снимая блокировку на разных элементах, и я могу следовать этому паттерну по мере движения. Это даёт ограниченное количество параллельности.

Если я хочу что-то убрать, я могу сделать это, используя перехватывающую блокировку.

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

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

Здесь есть пара коварных моментов. Например, как далеко я хочу телепортировать блокировку? Как далеко я хочу продвинуться в чтении перед тем как переместить блокировки? Если перемещение будет слишком коротким, я упущу возможность при ограниченной передающейся блокировке, считается, вам не нужны транзакции для удерживании одной блокировке при установке другой. А если я уйду слишком далеко, (например, переполню свой аппаратный буфер), тогда моя транзакция прервётся и весь этот труд, что я сейчас проделал, не приведёт ни к чему. Так что хитрость в том, чтобы понять, насколько телепортировать блокировку.

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

Вы установить ограничение, насколько далеко вы можете продвинуться. И после каждого успешного раза вы говорите: Хорошо, в следующий раз я продвинусь на один дальше. Так что если вы успешно телепортировали блокировку на 5 шагов, в следующий раз вы попробуете 6, а ещё в следующий 7. В какой-то момент вы выйдете за пределы. В таком случае вы устанавливаете ограничение в половину того, что у вас было в последний раз, и готово.

Вопросы для исследования

Напоследок я дам высокоуровневый короткий обзор открытых вопросов, на которые мы бы хотели знать ответы, но пока их точно не знает никто.

Блокировки

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

Управление памятью

Одна из областей, где транзакции оказались на удивление полезными управление памятью (как ручное, так и автоматическое). Malloc, free, сборка мусора... Если вы занимаетесь управлением памятью, то стремитесь совершать операции одного стиля, и хорошо понятно, какой объём работы вам придётся проделать. Это крайне важно, потому что программы постоянно распределяют и освобождают память. И мне кажется, транзакционная память уже показала, что может быть полезна здесь, но я считаю, что предстоит ещё много работы по улучшению.

БД

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

Энергетическая эффективность

Одна область, которая мне нравится и, как мне кажется, не получает достаточно внимания, это влияние на энергоэффективность, на архитектуру. Мы с моими коллегами из инженерного отдела работали над пониманием того, что энергетически эффективнее: блокировки или транзакции. Ваша микросхема скорее перегреется, если вы используете блокировки, или транзакционную память? И транзакционная память кажется более энергетически эффективной при большинстве условий из-за спекулятивного выполнения.

Графические процессоры

Была проведена большая работа над аппаратными ускорителями. GPU самый очевидный пример. Оказалось, что графические процессоры могут использовать аппаратные транзакции, опять же, они немного отличаются от многоядерных аппаратных транзакций. Но было очень полезно применять аппаратные транзакции и технологии аппаратных транзакций в графических процессорах.

ОС

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

Структуры данных

Проведена большая работа со структурами данных. Если вы наивно спроектировали структуру данных, оказалось, что транзакции могут не очень хорошо работать. Например, если в вашей хэш-таблице есть счётчик, который увеличивается с каждой операцией, то у вас не выйдет много параллельности со спекулятивными транзакциями, потому что все будут конфликтовать на счётчике. Поэтому это целое искусство проектировать структуры данных так, чтобы транзакции работали.

Архитектура компьютера

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

Есть понятие Кривая хайпа (hype curve). Она говорит, что при появлении новой идеи люди говорят: О! Это чудесно! Это решит все проблемы! Это первый верхний выступ. Потом они говорят: Ой, погодите-ка. Появляются всевозможные новые проблемы и задачи, может, это на самом деле плохо. А в итоге люди научаются решать задачи и всё становится нормально.

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

Транзакционные конструкции поддерживаются в C++, Haskell, других языках, они введены в архитектуры Intel и, очевидно, они уже никуда не денутся. Так что транзакции останутся надолго. И нам только нужно понять, как лучше их использовать.

Если заинтересовал этот доклад, обратите внимание на Hydra 2021: там снова выступит Морис Херлихи, а также будет много других заметных людей из мира распределённых и многопоточных систем. Конференция пройдёт с 15 по 18 июня в онлайне, программу и другую информацию можно увидеть на сайте.

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

Естественным перед началом анализа будет указание ограничений на ширину и глубину исследований. Принимаем, что многозадачность в рассматриваемых параллельных системах осуществляется простейшим путём - перегрузкой всего блока (связки) выполняющихся операторов (одновременное выполнение операторов разных программ не предполагается) или же система работает в однозадачном режиме; в противном случае высказанное в предыдущей фразе утверждение может быть неверным. Минимизация объёма устройств временного хранения данных (описано здесь http://personeltest.ru/aways/habr.com/ru/post/534722/) проводиться не будет. На этом этапе исследований также не учитываются задержки времени на обработку операторов и пересылку данных между ними (для системы SPF@home формально эти параметры могут быть заданы в файлах с расширениями med и mvr).

В предыдущей публикации http://personeltest.ru/aways/habr.com/ru/post/540122/ была описана технология получения ПВПП на основе модели потокового (Data-Flow) вычислителя. Обычно считают, что правила выбора операторов для выполнения в такой машине подчиняются логике действия некоторых сущностей, совместно выполняющих определённые действия актёров (actors); при этом естественным образом моделируются связанные с характеристиками времени параметры обработки операторов. В общем случае при этом отдельные операторы выполняются асинхронно. В публикации показано, что описанный принцип получения ПВПП приемлем (при выполнении несложных условий) и для машин архитектуры VLIW (Very Long Instruction Word, сверхдлинное машинное слово), отличающихся требованием одновременности начала выполнения всех операторов в связке. В расчётах использовали модель ILP (Instruction-LevelParallelism, параллелизм уровня машинных команд).

В рассматриваемый программный комплекс http://personeltest.ru/aways/habr.com/ru/post/530078/ включен модуль SPF@home, позволяющей работать с гранулами параллелизма любого размера (оператор любой сложности). Основным инструментом этого модуля является метод получения ярусно-параллельной формы (ЯПФ) графа алгоритма (здесь используется информационный граф, в котором вершинами являются узлы преобразования информации, а дугами её передачи).

Реформирование ЯПФ может дать результат, идентичный полученному моделированием выполнения программы на Data-Flow -машине, но в некоторых случаях результаты расходятся. В самом деле, это во многом различные подходы. Не столь сложно представить себе рой самостоятельных, взаимодействующих программ-актёров, выполняющих действия по поиску готовых к выполнению операторов, свободных в данный момент отдельных вычислителей и назначающих обработку выбранных операторов конкретному вычислителю etc etc, но действия эти логично производятся в RunTime и именно на границе (линии фронта) между уже выполненными и ещё не выполненными операторами (метафора поиска в ширину, а не в глубину в теории графов). При этом естественным образом создаётся очень подробный план выполнения параллельной программы с точными временными метками начала и конца выполнения операторов с привязкой их к конкретным вычислителям. Такой план хорош (с точностью до математической модели, которая в конечном счёте всегда в чём-то ограничена), однако автор сомневается в степени достаточной безумности практического использования полученного т.о. ПВПП

Метод обработки ЯПФ в целом более теоретичен и от многих особенностей абстрагирован, однако он может ещё до выполнения программы (DesignTime) показать ПВПП сверху (учитывая не только параллельный фронт выполнения операторов, но и всю карту боевых действий). Следствием большего абстрагирования ЯПФ-метода является субъективность интерпретации связи моментов обработки операторов с собственно ярусом ЯПФ. В самом деле, можно рассмотреть несколько укрупнённых подходов к таким интерпретациям; см. рис. ниже слева варианты a) и б) соответственно. На этом рисунке операторы показаны красными прямоугольниками, а яруса (в целях большей выразительности сказанного) - горизонтальными линиями:

• выполнение всех принадлежащих конкретному ярусу операторов начинается одновременно (тогда это фактически VLIW-идеологема и ПВПП изначально обладает ограниченностью, связанной с потерями времени на ожидание выполнения наиболее длительного оператора на ярусе; точное решение получается лишь при одинаковости времён выполнения всех операторов на ярусе);

• промежуток времени выполнения операторов может плавать относительно связанного с ярусом момента времени (возможна даже ограниченная асинхронность выполнения операторов).

При использовании ЯПФ в своих изысканиях Исследователь должен сам выбрать определённую модель и далее ей следовать. В рамках системы SPF@home, например, имеется возможность целевой реорганизации ЯПФ с конечной целью собрать на ярусах операторы с наиболее близкими длительностями обработки. Именно использование ЯПФ как нельзя лучше отвечает идеологеме EPIC (Explicitly Parallel Instruction Computing, явный параллелизм выполнения команд), позволяющей параллельной вычислительной системе выполнять инструкции согласно плану, заранее сформированному компилятором. Не следует игнорировать и субъективный фактор - бесспорным преимуществом ЯПФ является возможность простой и недвусмысленной визуализации собственно ПВПП.

Исходными данными для модуля SPF@home служат описания информационных графов алгоритма (программы) в стандартной DOT-форме (расширения файлов gv, могущие быть полученными импортом из модуля Data-Flow или иными путями). Допустимые (не нарушающие информационные связи в алгоритме) преобразования ЯПФ управляются программой на языке Lua, реализующей разработанные методы реструктуризации ЯПФ (дополнительная информация приведена в публикации http://personeltest.ru/aways/habr.com/ru/post/530078/). Эти методы неизбежно будут являться эвристическими вследствие невозможности прямого решения поставленных (относящихся к классу NP-полных) задач.

Т.о. вся ценность исследования сосредотачивается в разработке эвристических методов (эвристик) создания ПВПП при заданных целях и определённых ограничениях (напр., c учётом заданного поля параллельных вычислителей, максимума скорости выполнения, минимизации или ограничения размеров временного хранения данных и др.). Конечная цель работы встраивание этих алгоритмов в состав распараллеливающих компиляторов новых поколений.

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

В качестве пациентов использовались имеющиеся в наличии информационные графы алгоритмов, в основном класса линейной алгебры (как одни из наиболее часто встречающиеся в современных задачах обработки данных). По понятным причинам исследования проводились на данных небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера. Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач. При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow (http://personeltest.ru/aways/habr.com/ru/post/535926/) с последующим импортом в форме информационного графа в модуль SPF@home.

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

Ниже приведены результаты моделирования трёх наиболее часто встречающихся типов задач (в реальном случае обычно требуется выполнение нескольких из них одновременно):

1.Расписание выполнения программ на минимальном числе параллельных вычислителей при сохранении высоты ЯПФ

Фактически задача заключается в балансировке числа операторов по всем
ярусам ЯПФ (здесь балансировка стремление к достижению одинакового числа), причём идеалом является число операторов по уровням, равное средне-арифметическому (с округлением до целого вверх). Такая организация ЯПФ фактически позволяет увеличить плотность кода, недостатком которой часто страдают вычислители VLIW-архитектуры. Надо понимать, что данная постановка задачи имеет в большей степени методологическую ценность, ибо число физических параллельных вычислителей обычно много меньше ширины ЯПФ реальных задач.

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

Эмпирический метод 1-01_bulldozer имеет целью получение наиболее равномерного распределения операторов по ярусам ЯПФ без возрастания её высоты (сохранение времени выполнения программы); операторы переносятся только вниз (первоначально ЯПФ строится в верхнем варианте). Для этого метод старается перенести операторы с ярусов шириной выше среднего на яруса с наименьшей шириной. На каждом ярусе операторы перебираются в порядке очередности слева направо.

Метод 1-02_bulldozer является модификацией предыдущего с адаптацией. Для оператора с максимумом вариативности (назовём так диапазон возможного размещения операторов по ярусам ЯПФ без изменения информационных связей в графе алгоритма) в пределах яруса вычисляются верхний и нижний пределы его возможного расположения по ярусам.

В результирующей табл.1 рассматриваются: mnk_N программа аппроксимации методом наименьших квадратов N точек прямой, mnk_2_N то же, но квадратичной функцией, korr_N вычисление коэффициента парной корреляции по N точкам, slau_N решение системы линейных алгебраических уравнений порядка N прямым (не итерационным) методом Гаусса, m_matr_N - программа умножения квадратных матриц порядка N традиционным способом, m_matr_vec_N умножение квадратной матрицы на вектор, squa_equ_2 решение полного квадратного уравнения в вещественных числах, squa_equ_2.pred то же, но с возможностью получения вещественных и мнимых корней при использовании метода предикатов для реализации условного выполнения операторов, e17_o11_t6, e313_o206_t32, e2367_o1397_t137, e451_o271_t30, e916_o624_t89, e17039_o9853_t199 сгенерированные специальной программой по заданным параметрам информационного графа. Вычислительную трудность преобразования будем характеризовать числом перемещений операторов с яруса на ярус. Неравномерность распределения числа операторов по ярусам ЯПФ характеризуется коэффициентом неравномерности (отношение числа операторов на наиболее и наименее нагруженных ярусов соответственно).

Для удобства анализа в таблице цветом выделены ячейки, соответствующие случаю достижению снижения ширины без возрастания высоты ЯПФ, а жирным начертанием цифр величины для сравнения.

Как видно из табл.1, во многих случаях удается значительно (до 1,5-2 раз) снизить ширину ЯПФ, но почти никогда до минимальной величины (средне-арифметическое значение ширин ярусов). В целом эвристика 1-02_bulldozer несколько более эффективна, но проигрывает по вычислительной сложности. В большинстве случаев увеличение размера обрабатываемых данных повышает эффективность балансировки (очевидно, это связано с повышением числа степеней свободы ЯПФ).

Интересно, что для некоторых алгоритмов (напр., slau_N) ни один из предложенных методов не дал результата. Сложность балансировки ЯПФ связана с естественным стремлением разработчиков алгоритмов создавать максимально плотные записи последовательности действий.

2.Расписания выполнения программ на фиксированном числе параллельных вычислителей при возможности увеличения высоты ЯПФ

Практический интерес представляют методы с увеличением высоты ЯПФ (см. табл.2, в которой дано сравнение двух методов с метафорическими названиями Dichotomy и WidthByWidth); при этом приходится смириться с увеличение времени выполнения программы. В ходе вычислительных экспериментов задавалась конечная ширина преобразованной ЯПФ (отдельные столбцы в правой части табл.2). Количественные параметры преобразований выдавались в форме частного, где числитель и знаменатель показывают число перемещений (первая строка), высоту ЯПФ (вторая) и коэффициент ковариации CV (третья строка) для каждого исследованного графа. Характеризующий неравномерность распределения ширин ярусов коэффициент ковариации рассчитывался как CV=/W, где - среднеквадратичное отклонение числа операторов по всем ярусам ЯПФ, W - среднеарифметическое числа операторов по ярусам.

Эвристика Dichotomy предполагает для разгрузки излишне широких ярусов перенос половины операторов на вновь созданный ярус под текущим, эвристика WidthByWidth реализует постепенный перенос операторов на вновь создаваемые яруса ЯПФ. Из табл.2 видно, что метод WidthByWidth в большинстве случаев приводит к лучшим результатам, нежели Dichotomy (например, высота преобразованной ЯПФ существенно меньше что соответствует снижению времени выполнения параллельной программы притом за меньшее число перемещений операторов).

3.Расписание выполнения программ на фиксированном числе гетерогенных параллельных вычислителей

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

Модуль SPF@home поддерживает эту возможность путём сопоставления информации из двух файлов для операторов и вычислителей (*.ops и *.cls соответственно). Имеется возможность задавать совпадение по множеству свободно назначаемых признаков для любого диапазона операторов/вычислителей. Условием выполнимости данного оператора на заданном вычислителе является minVal_1Val_1maxVal_1 для одинакового параметра (Val_1, minVal_1, maxVal_1 числовые значения данного параметра для оператора и вычислителя соответственно).

Разработка расписания для выполнения программы на гетерогенном поле параллельных вычислителей является более сложной процедурой относительно вышеописанных и здесь упор делается на программирование на Lua (API-функции системы SPF@home обеспечивают минимально необходимую поддержку). Т.к. на одном ярусе ЯПФ могут находиться операторы, требующие для выполнения различных вычислителей, полезным может служить концепция расцепления ярусов ЯПФ на семейства подъярусов, каждое из которых соответствует блоку вычислителей c определёнными возможностями (т.к. все данного операторы яруса обладают ГКВ-свойством, последовательность выполнения их в пределах яруса/подъяруса в первом приближении произвольна). На схеме ниже слева показано расщепление операторов на одном из ярусов ЯПФ в случае наличия 6 параллельных вычислителей 3-х типов.

Пример плана выполнения программы на поле из 3-х типов параллельно работающих вычислителей (c количествоv 5,3,4 штук соответственно и номерами 1-5, 6-8, 9-12 по типам, всего 12 штук) приведён в табл.3. При расчёте в качестве исходной использовался конкретный алгоритм, характеризующийся ЯПФ с числом операторов 206 и дуг 323, ярусов 32 (после расчета подъярусов получилось 48). Первый столбец таблицы показывает (разделитель символ прямого слеша) номер яруса/подъяруса; в ячейках таблицы приведены номера операторов, сумма их числа по подъярусам равно числу операторов на соответствующем ярусе ЯПФ.

Моделирование, результат которого приведён в табл.3, может быть использовано в форме решения обратной задачи при определении оптимального числа параллельных вычислителей различного типа для выполнения заданных алгоритмов (групп алгоритмов).

В самом деле, в рассматриваемом случае общее время T решения задачи определяется суммой по всем ярусам максимальных значений времён выполнения операторов на подъярусах данного яруса, т.к. группы операторов на подъярусах выполняются последовательно (первая сумма берётся по j, вторая по i, максимум по k_j):

T=(maxt_ik),

где j - число ярусов ЯПФ, i - число подъярусов на данном ярусе, k_{j -} типы вычислителей на j-том ярусе, t_{ik -} время выполнения оператора типа i на вычислителе типа k. Если ставится задача достижения максимальной производительности, вполне возможно определить число вычислителей конкретного типа, минимизирующее T (напр., для показанного табл.3 случая количество вычислителей типа II полезно увеличить в пику вычислителяv типа I).

Задача минимизации общего времени решения T усложняется в случае возможности выполнения каждого оператора на нескольких вычислителях вследствие неоднозначности t_ik в вышеприведённом выражении; здесь необходима дополнительная балансировка по подъярусам.

Описание параметров операторов располагается в файлах с расширением ops, параметров вычислителей cls; соответствующая API-функция (обёрнутая Lua-вызовом) возвращает значение, разрешающее или запрещающее выполнение данного оператора на заданном вычислителе. Описанные файлы являются текстовыми (формат данных определён в документации), что даёт возможность разработки внешних программ для генерации требуемого плана эксперимента с использованием модуля SPF@home в режиме командной строки.

В порядке обсуждения небезынтересно будет рассмотреть вариант ЯПФ в нижней форме (при этом все операторы перемещены максимально в сторону окончания выполнения программы). Такая ЯПФ может быть получена из верхней перемещениями операторов по ярусам как можно ниже или проще построением ЯПФ в направлении от конца программы к её началу. Ниже проиллюстрировано сравнение распределения ширин ЯПФ в верхней и нижней формах (изображения в строке слева и справа соответственно в 4-х рядах) для алгоритма умножения матриц традиционным способом при порядках матриц N=3,5,7,10. Здесь H, W и W высота, ширина и среднеарифметическая ширина ЯПФ (последняя показана на рисунках пунктиром; символ прямого слеша разделяет параметры для верхней и нижней ЯПФ (фиолетовый цвет ярус максимальной ширины, красный минимальной).

Соответствующие иллюстрации для процедуры решения систем линейных алгебраических уравнения порядков N=3,5,7,10 безытерационным методом Гаусса представлены ниже.

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

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

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

Выше использованные количественные характеристики неравномерности не дают информации о форме кривой, обладающей этой неравномерностью. В качестве дополнительной оценки неравномерности распределения операторов по ярусам ЯПФ может быть признан известный графо-аналитического метод определения дифференциации доходов населения, заключающегося в расчёте численных параметров расслоения (кривая Лоренца и коэффициент Джини), несмотря на зеркально-противоположную форму анализируемых кривых. Удобство сравнения ЯПФ различных алгоритмов достигается нормированием обоих осей графиков на общую величину (единицу или 100%).

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

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

Итак, программная система SPF@home выполняет практическую задачу по составлению расписаний выполнения заданных алгоритмов (программ) на заданном поле параллельных вычислителей и дает возможность проводить различного типа исследования свойств алгоритмов (в данном случае оценивать вычислительную сложность методов составления расписаний). Система нацелена в основном на анализ программ, созданных с использованием языков программирования высокого уровня без явного указания распараллеливания и в системах c концепцией ILP (Instruction-LevelParallelism, параллелизм на уровне команд), хотя возможности модуля SPF@home позволяют использовать в качестве неделимых блоков последовательности команд любого размера.

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

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

Предыдущие публикации на тему исследования параметров функционирования вычислительных систем методами математического моделирования:

• Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом (http://personeltest.ru/aways/habr.com/ru/post/530078/, 26.11.2021)

• Такие важные короткоживущие данные (http://personeltest.ru/aways/habr.com/ru/post/534722/, 24.12.2021)

• Это непростое условное выполнение (http://personeltest.ru/aways/habr.com/ru/post/535926/, 03.01.2021)

• Динамика потокового вычислителя (http://personeltest.ru/aways/habr.com/ru/post/540122/, 01.02.2021).

Основные данные вычислительных экспериментов по реорганизации ярусно-параллельной формы (ЯПФ) информационных графов алгоритмов (ТГА) приведены в предыдущей публикации (http://personeltest.ru/aways/habr.com/ru/post/545498/). Цель текущей публикации показать окончательные результаты исследований разработки расписаний выполнения параллельных программ в показателях вычислительной трудоёмкости собственно преобразования и качества полученных расписаний. Данная работа является итогом вполне определённого цикла исследований в рассматриваемой области.

Как и было сказано ранее, вычислительную трудоёмкости (ВТ) в данном случае будем вычислять в единицах перемещения операторов с яруса на ярус в процессе реорганизации ЯПФ. Этот подход близок классической методике определения ВТ операций упорядочивания (сортировки) числовых массивов, недостатком является неучёт трудоёмкости процедур определения элементов для перестановки.

Т.к. в принятой модели ЯПФ фактически определяет порядок выполнения операторов параллельной программы (операторы выполняются группами по ярусам поочерёдно), в целях сокращения будем иногда использовать саму аббревиатуру ЯПФ в качестве синонима понятия плана (расписания) выполнения параллельной программы. По понятным причинам исследования проводились на данных относительно небольшого объёма в предположении сохранения корректности полученных результатов при обработке данных большего размера. Описанные в данной публикации исследования имеют цель продемонстрировать возможности имеющегося инструментария при решении поставленных задач. При желании возможно исследовать произвольный алгоритм, описав и отладив его в модуле Data-Flow (http://personeltest.ru/aways/habr.com/ru/post/535926/) с последующим импортом в формате информационного графа в модуль SPF@home для дальнейшей обработки.

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

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

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

Полученные результаты предназначаются для улучшения качества разработки расписаний выполнения параллельных программ в распараллеливающих компиляторах будущих поколений. При этом внутренняя реализация данных конечно, совсем не обязана предусматривать явного построения ЯПФ в виде двумерного массива, как для большей выпуклости показано на рис.2 в публикации http://personeltest.ru/aways/habr.com/ru/post/530078/ и выдаётся программным модулем SPF@home (http://vbakanov.ru/spf@home/content/install_spf.exe). Она может быть любой удобной для компьютерной реализации например, в наивном случае устанавливающей однозначное соответствие между формой ИГА в виде множества направленных дуг {k,l} (матрица смежности) и двоек номеров вершин i_k,j_k и i_l,j_l, где i,j номера строк и столбцов в ЯПФ (процедуру преобразования ИГА в начальную ЯПФ провести всё равно придётся, ибо в данном случае именно она выявляет параллелизм в заданном ИГА алгоритме; только после этого можно начинать любые преобразования ЯПФ).

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

Для каждой из группы рассматриваемых задач (преобразования с сохранением высоты исходной ЯПФ или при возможности увеличения высоты оной) рассмотрим по две методики (эвристики, ибо так согласились именовать разработки) для перового случая это 1-01_bulldozer vs 1-02_bulldozer, для второго - WidthByWidtn vs Dichotomy. Мне стыдно повторять это, но высота ЯПФ определяет время выполнения программы

1. Получение расписания параллельного выполнения программ при сохранении высоты ЯПФ

Сохранение высоты исходной ЯПФ равносильно выполнению алгоритма (программы) за минимально возможное время. Наиболее равномерная нагрузка на все вычислители параллельной системы будет при одинаковой ширине всех ярусов ЯПФ (среднеарифметическое значение). В ЯПФ реальных алгоритмов и размерности обрабатываемых данных среднеарифметическое значение является довольно большим (практически всегда много большим числа отдельных вычислителей в параллельной системе). Т.о. рассматриваемый случай не часто встречается в практике, но всё же должен быть разобран.

Для сравнения выберем часто анализируемые ранее алгоритмы и два эвристических метода целенаправленного преобразования их ЯПФ эвристики 1-01_bulldozer и 1-02_bulldozer.

Результаты применения этих эвристик приведены на рис. 1-3; обозначения на этих рисунках (по осям абсцисс отложены показатели размерности обрабатываемых данных):

• графики a), b) и с) ширина ЯПФ, коэффициент вариации (CV ширин ярусов ЯПФ), число перемещений (характеристика вычислительной трудоёмкости) операторов соответственно;

• сплошные (красная), пунктирные (синяя) и штрих-пунктирные (зелёная) линии исходные данные, результат применения эвристик 1-01_bulldozer и 1-02_bulldozer cответственно.

Данные рис. 1-3 показывают, что во многих случаях удаётся приблизиться к указанной цели. Напр., рис. 1a) иллюстрирует снижение ширины ЯПФ до 1,7 раз (метод 1-01_bulldozer) и до 3 раз (метод 1-02_bulldozer) при умножении матриц 10-го порядка.

Коэффициент вариации ширин ярусов ЯПФ (рис. 1b) приближается к 0,3 (граница однородности набора данных) при использовании эмпирики 1-02_bulldozer и, что немаловажно, достаточно стабилен на всём диапазоне размерности данных.

Трудоёмкость достижения результата (рис. 1c) при использовании метода 1-02_bulldozer значительно ниже (до 3,7 раз при порядке матриц 10) метода 1-01_bulldozer.

Важно, что эффективность метода возрастает с ростом размерности обрабатываемых данных.

Не менее эффективным показал себя метод 1-02_bulldozer на алгоритме вычисления коэффициента парной корреляции (рис. 2).

Попытка реорганизации ЯПФ алгоритма решения системы линейных алгебраических уравнений (СЛАУ) порядка до 10 обоими методами (рис. 3) оказалась малополезной. Ширину ЯПФ снизить не удалось вообще (рис. 3a), снижение CV очень мало (рис. 3b), однако метод 1-02_bulldozer немного выигрывает в трудоёмкости (рис. 3c).

Для большей полноты выводов объём исследований должен быть расширен, однако уже сейчас ясно, далеко не каждый метод реорганизации ЯПФ одинаково эффективен для преобразования (в смысле построения рационального расписания параллельного выполнения) различных алгоритмов. Т.к. принятый в данной работе общий подход предполагает итеративное приближение к наилучшему решению поставленной задачи, надлежит продолжить разработку новых эвристик (с учётом достигнутого).

2. Получение расписания параллельного выполнения программ на фиксированном числе параллельных вычислителей

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

Ниже рассматривается распространенный случай выполнения программы на заданном гомогенном поле из W параллельных вычислителей (от W=W₀ до W=1, где W₀ ширина ЯПФ, а нижняя граница соответствует полностью последовательному выполнению). Сравниваем два метода реорганизации ЯПФ Dichotomy и WidthByWidtn:

• Dichotomy. Цель получить вариант ЯПФ с c шириной не более заданного W c увеличением высоты методом перенесения операторов с яруса на вновь создаваемый ярус ниже данного. Если ширина яруса выше W, ровно половина операторов с него переносится на вновь создаваемый снизу ярус и так далее, пока ширина станет не выше заданной W. Метод работает очень быстро, но грубо (высота ЯПФ получается явно излишней и неравномерность ширин ярусов высока).

• WidthByWidtn. Подлежат переносу только операторы яруса с числом операторов выше заданного N>W путём создания под таким ярусом число ярусов М, равное:

Особенностью этой эвристики является правило выбора конкретных операторов, подлежащих переносу на вновь создаваемые ярусы.

На рис. 4,5 показаны результаты выполнения указанных эвристик в применении к двум распространенным алгоритмам линейной алгебры - умножение квадратных матриц классическим методом и решение системы линейных алгебраических уравнений прямым (неитерационным) методом Гаусса; красные и синие линии на этих и последующих рисунках соответствуют эвристикам WidthByWidtn и Dichotomy соответственно. Не забываем, что ширина реформированной ЯПФ здесь соответствует числу команд в связке сверхдлинного машинного слова.

Как видно из рис. 4 и 5, оба метода на указанных алгоритмах приводят к близким результатам (из соображений представления ЯПФ плоской таблицей и инвариантности общего числа операторов в алгоритме это, конечно, гипербола!). При большей высоте ЯПФ увеличивается время жизни данных, но само их количество в каждый момент времени снижается.

Однако при всех равно-входящих соответствующие методу WidthByWidtn кривые расположены ниже, нежели по методу Dichotomy; это соответствует несколько большему быстродействию. Полученные методом WidthByWidtn результаты практически совпадают с идеалом высоты ЯПФ, равным N_сумм./W_средн. , где N_сумм. общее число операторов, W_средн. среднеарифметическое числа операторов по ярусам ЯПФ при заданной ширине ея.

Анализ результатов, приведённый на рис. 6 и 7, более интересен (хотя бы потому, что имеет чисто практический интерес вычислительную трудоёмкость преобразования ЯПФ). Как видно из рис. 6 и 7, для рассмотренных случаев метод WidthByWidtn имеет меньшую (приблизительно в 3-4 раза) вычислительную трудоёмкость (в единицах числа перестановок операторов с яруса на ярус) относительно метода Dichotomy (хотя на первый взгляд ожидается обратное). Правда, при этом метод (эвристика) WidthByWidtn обладает более сложной внутренней логикой по сравнению с Dichotomy (в последнем случае она примитивна).

Т.о. проведено сравнение методов реорганизации (преобразования) ЯПФ конкретных алгоритмов с целью их параллельного выполнения на заданном числе вычислителей. Сравнение проведено по критериям вычислительной трудоёмкости преобразований и неравномерности загрузки параллельной вычислительной системы.

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

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

Предыдущие публикации на тему исследования параметров функционирования вычислительных систем методами математического моделирования:

• Есть ли параллелизм в произвольном алгоритме и как его использовать лучшим образом (http://personeltest.ru/aways/habr.com/ru/post/530078/, 26.11.2021)

• Такие важные короткоживущие данные (http://personeltest.ru/aways/habr.com/ru/post/534722/, 24.12.2021)

• Это непростое условное выполнение (http://personeltest.ru/aways/habr.com/ru/post/535926/, 03.01.2021)

• Динамика потокового вычислителя (http://personeltest.ru/aways/habr.com/ru/post/540122/, 01.02.2021)

• Параллелизм и плотность кода (http://personeltest.ru/aways/habr.com/ru/post/545498/, 05.03.2021)

• Сколько стоит расписание (http://personeltest.ru/aways/habr.com/ru/post/551688/, 10.04.2021) - текущая

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

Но перед тем, как начать, т. к. статья будет длинной, я хотел бы обозначить основные моменты:

• Используйте функции и модули для разделения мыслительных сущностей.

• Используйте процессы для разделения сущностей времени выполнения.

• Не используйте процессы (даже агентов) для разделения сущностей мышления.

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

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

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

Пример

Но как же тогда управлять сложным состоянием, если не с помощью агентов и процессов? Позвольте мне проиллюстрировать эту идею на простой предметной модели сокращенной и слегка модифицированной версии игры в блэкджек. Код, который я вам покажу (доступен здесь), запускает один раунд на столе для блэкджека.

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

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

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

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

Границы процесса

Итак, нам нужно отслеживать различные типы состояний, которые меняются с течением времени: колода карт, руки каждого игрока и состояние раунда. Наивный подход к этому - использование нескольких процессов. У нас может быть один процесс для каждой руки, другой процесс для колоды карт и главный процесс, который управляет всем раундом. Я вижу, что люди иногда используют аналогичный подход, но я совершенно не уверен, что это правильный путь. Основная причина в том, что игра по своей природе очень синхронизирована. Все происходит одно за другим в четко определенном порядке: я получаю свои карты, делаю один или несколько ходов, и когда я закончу, вы будете следующим. В любой момент времени в одном раунде происходит только одно действие.

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

Итак, в этом случае я вижу много потенциальных недостатков и не очень много преимуществ от использования нескольких процессов для управления состоянием одного раунда. Однако разные раунды взаимно независимы. У них есть свои отдельные потоки, они держат свои отдельные состояния, у них нет ничего общего. Таким образом, управление несколькими раундами в одном процессе контрпродуктивно. Это увеличит нашу поверхность ошибок (сбой в одном раунде приведет к отключению всего) и, возможно, приведет к снижению производительности (мы не используем несколько ядер) или узким местам (длительная обработка в одном раунде парализует все остальные). Если мы будем запускать разные раунды в разных процессах, есть очевидные выигрыши, так что это решение не составит труда :-) (прим. переводчика: Как же нет ничего общего, а состояние кошельков игроков?)

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

Итак, учитывая все обстоятельства, я почти уверен, что единственный процесс для управления всем состоянием одного раунда - это правильный путь. Было бы интересно посмотреть, что изменится, если мы введем концепцию стола, где раунды играются постоянно, а игроки меняются со временем. Я не могу сказать наверняка на данный момент, но я думаю, что это интересное упражнение на случай, если вы захотите его изучить :-)

Функциональное моделирование

Итак, как же мы можем разделить разные сущности без использования нескольких процессов? Конечно, используя функции и модули. Если мы распределим разные части логики по разным функциям, дадим этим функциям собственные имена и, возможно, организуем их в правильно названные модули, мы сможем прекрасно представить наши идеи без необходимости имитировать объекты с помощью агентов.

Позвольте мне показать вам, что я имею в виду, проведя вас через каждую часть моего решения, начиная с самого простого.

Колода карт

Первое, что я хочу запечатлеть - это колода карт. Мы хотим смоделировать стандартную колоду из 52 карт. Мы хотим начать с перетасованной колоды, а затем иметь возможность брать из нее карты одну за другой.

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

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

@cards (  for suit <- [:spades, :hearts, :diamonds, :clubs],      rank <- [2, 3, 4, 5, 6, 7, 8, 9, 10, :jack, :queen, :king, :ace],    do: %{suit: suit, rank: rank})

Теперь я могу добавить функцию shuffle/0 для создания перемешанной колоды:

def shuffled(), do:  Enum.shuffle(@cards)

И наконец, take/1, которая берёт верхнюю карту из колоды:

def take([card | rest]), do:  {:ok, card, rest}def take([]), do:  {:error, :empty}

Функция take/1 возвращает либо {:ok, card_taken, rest_of_the_deck}, либо {:error, :empty}. Такой интерфейс заставляет клиента (пользователя абстракции колоды) явно решать, как поступать в каждом случае.

Как мы можем это использовать:

deck = Blackjack.Deck.shuffled()case Blackjack.Deck.take(deck) do  {:ok, card, transformed_deck} ->    # do something with the card and the transform deck  {:error, :empty} ->    # deck is empty -> do something elseend

Это пример того, что я люблю называть функциональной абстракцией, что является причудливым названием для:

• кучи связанных функций,

• с описательными именами,

• которые не проявляют побочных эффектов,

• и могут быть извлечены в отдельный модуль

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

Не так важно, находятся ли эти функции в выделенном модуле. Код этой абстракции довольно прост и используется только в одном месте. Поэтому я мог бы также определить приватные функции shuffled_deck/0 и take_card/1 в клиентском модуле. Фактически, это то, что я часто делаю, если код достаточно мал. Я всегда могу выделить это позже, если что-то усложнится. (прим. переводчика: не совсем уловил здесь мысль, которую хотел донести автор)

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

Полный код модуля доступен здесь.

Рука

Эту же технику можно использовать для управления рукой. Эта абстракция отслеживает карты в руке. Она также умеет подсчитывать очки и определять статус руки (:ok или :busted). Реализация находится в модуле Blackjack.Hand.

Модуль выполняет две функции. Мы используем new/0 для создания экземпляра руки, а затем deal/2, чтобы раздать карту руке. Вот пример комбинации руки и колоды:

# create a deckdeck = Blackjack.Deck.shuffled()# create a handhand = Blackjack.Hand.new()# draw one card from the deck{:ok, card, deck} = Blackjack.Deck.take(deck)# give the card to the handresult = Blackjack.Hand.deal(hand, card)

Результат deal/2 вернётся в форме {hand_status, transformed_hand}, где hand_status это или :ok или :busted.

Раунд

Эта абстракция, реализованная в модуле Blackjack.Round, связывает всё воедино. Она имеет следующие обязанности:

• сохранять состояния колоды

• держать состояние всех рук в раунде

• решать, кому переходит следующий ход

• получать и интерпретировать ход игрока (хит / стоп)

• брать карты из колоды и передавать их текущей руке

• вычислять победителя после того, как все руки разыграны

Абстракция раунда будет следовать тому же функциональному подходу, что и колода с рукой. Однако здесь есть дополнительный поворот, который касается выделения темпоральной логики. Раунд занимает некоторое время и требует взаимодействия с игроками. Например, когда начинается раунд, первый игрок должен быть проинформирован о первых двух картах, которые он получил, а затем он должен быть проинформирован о том, что пришла его очередь сделать ход. Затем раунду нужно дождаться, пока игрок сделает ход, и только после этого он сможет пойти дальше.

У меня сложилось впечатление, что многие люди, включая опытных эрлангистов/эликсирщиков, реализовали бы концепцию раунда непосредственно в GenServer или в :gen_statem. Это позволит им управлять состоянием раунда и темпоральной логикой (например, общением с игроками) в одном месте.

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

Я не хочу объединять эти две сложные задачи вместе, потому что они запутаются, и с кодом будет труднее работать. Я хочу перенести временные проблемы в другое место и получить чистую предметную модель раунда блэкджека.

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

Позвольте показать вам код. Чтобы создать новый раунд, мне нужно вызвать start/1:

{instructions, round} = Blackjack.Round.start([:player_1, :player_2])

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

• создание руки для каждого игрока

• отслеживание текущего игрока

• отправка уведомлений игрокам

  Функция возвращает кортеж. Первый элемент кортежа - это список инструкций. Пример:

  [{:notify_player, :player_1, {:deal_card, %{rank: 4, suit: :hearts}}},{:notify_player, :player_1, {:deal_card, %{rank: 8, suit: :diamonds}}},{:notify_player, :player_1, :move}]
  

  Инструкции - это способ, которым абстракция информирует своего клиента о том, что необходимо сделать. Как только мы начинаем раунд, в первую руку передаются две карты, а затем экземпляр раунда ожидает хода игрока. Итак, в этом примере абстракция инструктирует нас:

• уведомить игрока 1, что он получил четвёрку червей

• уведомить игрока 1, что он получил восьмёрку бубён

• уведомить игрока 1, что ему нужно сделать ход

  Фактическая доставка этих уведомлений заинтересованным игрокам является ответственностью клиентского кода. Клиентским кодом может быть, скажем, GenServer, который будет отправлять сообщения процессам игроков. Он также будет ждать, пока игроки не сообщат, когда они захотят взаимодействовать с игрой. Это временная(темпоральная) логика, и она полностью хранится за пределами модуля Round.

Второй элемент возвращённого кортежа, называется round, это состояние самого раунда. Стоит отметить, что эти данные типизированы как непрозрачные. Это значит, что клиент не может читать эти данные внутри переменной round. Всё, что нужно клиенту, будет доставлено в списке instruction.

Давайте продвинемся на шаг вперед в этом раунде, взяв следующую карту игроком 1:

{instructions, round} = Blackjack.Round.move(round, :player_1, :hit)

Мне нужно передать идентификатор игрока, чтобы абстракция могла проверить, правильный ли игрок делает ход. Если я передам неверный идентификатор, абстракция попросит меня уведомить игрока, что сейчас не его ход.

Вот инструкции, которые я получил:

[  {:notify_player, :player_1, {:deal_card, %{rank: 10, suit: :spades}}},  {:notify_player, :player_1, :busted},  {:notify_player, :player_2, {:deal_card, %{rank: :ace, suit: :spades}}},  {:notify_player, :player_2, {:deal_card, %{rank: :jack, suit: :spades}}},  {:notify_player, :player_2, :move}]

Этот список говорит мне, что игрок 1 получил десятку пик. Поскольку раньше у него было 4 червы и 8 бубён, игрок вылетает из игры, и раунд немедленно переходит к следующей руке. Клиенту предлагается уведомить игрока 2 о том, что у него есть две карты, и что он должен сделать ход.

Сделаем ход от имени игрока 2:

{instructions, round} = Blackjack.Round.move(round, :player_2, :stand)# instructions:[  {:notify_player, :player_1, {:winners, [:player_2]}}  {:notify_player, :player_2, {:winners, [:player_2]}}]

Игрок 2 не взял другую карту, поэтому его рука завершена. Абстракция немедленно определяет победителя и инструктирует нас проинформировать обоих игроков о результате.

Давайте посмотрим, как Round прекрасно сочетается с абстракциями Deck и Hand. Следующая функция из модуля Round берет карту из колоды и передает ее текущей руке:

defp deal(round) do  {:ok, card, deck} =    with {:error, :empty} <- Blackjack.Deck.take(round.deck), do:      Blackjack.Deck.take(Blackjack.Deck.shuffled())  {hand_status, hand} = Hand.deal(round.current_hand, card)  round =    %Round{round | deck: deck, current_hand: hand}    |> notify_player(round.current_player_id, {:deal_card, card})  {hand_status, round}end

Берём карту из колоды, используя новую колоду, если текущая закончилась. Затем мы передаем карту в текущую руку, обновляем раунд новой рукой и статусом колоды, добавляем инструкцию по уведомлению о данной карте и возвращаем статус руки (:ok или :busted) и обновленный раунд. Никаких дополнительных процессов в этом процессе не задействовано :-)

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

Но благодаря механизму инструкций, ничего из этого не случилось, и модуль Round остался сфокусированным на правилах игры. Функция notify_player будет сохранять инструкцию. Позже, перед выходом, функция take_instructions из Round будет забирать все ожидающие инструкции, и возвращать их по отдельности, вынуждая клиентский код интерпретировать их.

В качестве бонуса, этот код теперь может быть использован разными типами клиентов. В примерах выше, я дёргал его вручную из сессии. Другой пример - вызывать этот код в тестах. Эта абстракция теперь может быть легко протестирована, без необходимости производить сайд эффекты или наблюдать их.

Организация процесса

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

Сервер раунда

Каждый раунд управляется модулем Blackjack.RoundServer, который есть GenServer. Agent также мог бы подойти для этих целей, но я не фанат агентов, так что я остановлюсь на GenServer. Ваши предпочтения могут отличаться, конечно, и я полностью уважаю ваше мнение :-)

Чтобы запустить процесс, нам нужно вызвать функцию start_playing/2. Это имя выбрано вместо более распространенного start_link, поскольку start_link по соглашению ссылается на вызывающий процесс. Напротив, start_playing начнет раунд где-то еще в дереве надзора, и процесс не будет связан с вызывающим.

Функция принимает два аргумента: идентификатор раунда и список игроков. Идентификатор раунда - это произвольный уникальный терм, который должен быть выбран клиентом. Серверный процесс будет зарегистрирован во внутреннем реестре с использованием этого идентификатора.

Каждая запись в списке игроков представляет собой словарь, описывающий клиентскую часть игрока:

@type player :: %{id: Round.player_id, callback_mod: module, callback_arg: any}

Игрок описывается его идентификатором, модулем обратного вызова и аргументом обратного вызова. Идентификатор будет передан абстракции раунда. Всякий раз, когда абстракция инструктирует сервер уведомить некоторого игрока, сервер вызывает callback_mod.some_function (some_arguments), где some_arguments будет включать идентификатор раунда, идентификатор игрока, callback_arg и дополнительные аргументы, специфичные для уведомления.

Подход callback_mod позволяет нам поддерживать различные типы игроков, такие как:

• игроков, подключенных через HTTP

• игроков, подключенных через настраиваемый протокол TCP

• игрок в сеансе оболочки iex

• автоматических игроков (ботов)

  Мы легко справимся со всеми этими игроками в одном раунде. Сервер не заботится ни о чём из этого, он просто вызывает функции обратного вызова модуля обратного вызова и позволяет реализации выполнять работу.

Функции, которые должны быть реализованы в модуле обратного вызова, перечислены здесь:

@callback deal_card(RoundServer.callback_arg, Round.player_id,  Blackjack.Deck.card) :: any@callback move(RoundServer.callback_arg, Round.player_id) :: any@callback busted(RoundServer.callback_arg, Round.player_id) :: any@callback winners(RoundServer.callback_arg, Round.player_id, [Round.player_id])  :: any@callback unauthorized_move(RoundServer.callback_arg, Round.player_id) :: any

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

Другое приятное следствие такого дизайна - это то, что тестирование этого сервера довольно просто. Тест реализует уведомления путём отправки сообщений самому себе из каждого колбека. Затем тестирование сводится к asserting/refuting определённых сообщений, и вызову RoundServer.move/3, чтобы сделать ход от имени игрока.

Отправка сообщений

Когда функция модуля Round возвращает список инструкций серверному процессу, тот пройдёт по этому списку, и интерпретирует инструкции.

Сами уведомления отправляются из отдельных процессов. Это пример, в котором мы можем получить преимущество от дополнительного параллелизма. Отправка уведомлений - это задача, отдельная от задачи управления состоянием раунда. Логика уведомлений может быть перегружена такими задачами, как медленные или отключенные клиенты, поэтому стоит делать это вне раунда. Более того, уведомления разным игрокам не имеют ничего общего, поэтому их можно отправлять из разных процессов. Однако нам нужно сохранить порядок уведомлений для каждого игрока, поэтому нам нужен отдельный процесс уведомления для каждого игрока.

Это реализовано в модуле Blackjack.PlayerNotifier, процессе на основе GenServer, чья роль - отправлять уведомление отдельному игроку. Когда мы стартуем сервер раунда функцией start_playing/2, запускается небольшое поддерево надзора в котором размещается сервер раунда вместе с одним сервером уведомлений на каждого игрока в раунде.

Когда сервер раунда делает ход, он получает список инструкций от абстракции раунда. Затем он перенаправляет каждую инструкцию соответствующему серверу уведомлений, который интерпретирует эту инструкцию и вызывает соответствующий модуль/функцию/аргументы(M/F/A) для уведомления игрока.

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

[  {:notify_player, :player_1, {:deal_card, %{rank: 10, suit: :spades}}},  {:notify_player, :player_1, :busted},  {:notify_player, :player_2, {:deal_card, %{rank: :ace, suit: :spades}}},  {:notify_player, :player_2, {:deal_card, %{rank: :jack, suit: :spades}}},  {:notify_player, :player_2, :move}]

Может случиться так, что сообщения player_2 придут до того, как player_1 будет проинформирован о том, что он остановлен. Но это нормально, ведь это два разных игрока. Порядок сообщений для каждого игрока, конечно же, сохраняется, благодаря процессу сервера уведомлений, зависящему от конкретного игрока.

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

Сервис блэкджека

Картинка завершается в виде приложения OTP :blackjack (модуль Blackjack). Когда вы запускаете приложение, запускается пара локально зарегистрированных процессов: экземпляр внутреннего реестра Registry (используется для регистрации серверов раунда и уведомлений) и супервизор :simple_one_for_one, который будет размещать поддерево процесса для каждого раунда.

Это приложение теперь в основном представляет собой сервис блэкджека, который может управлять несколькими раундами. Сервис является универсальным и не зависит от конкретного интерфейса. Вы можете использовать его с Phoenix, Cowboy, Ranch (для простого TCP), elli или любым другим, подходящим для ваших целей. Вы реализуете модуль обратного вызова, запускаете клиентские процессы и запускаете сервер раунда.

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

$ iex -S mixiex(1)> Demo.runplayer_1: 4 of spadesplayer_1: 3 of heartsplayer_1: thinking ...player_1: hitplayer_1: 8 of spadesplayer_1: thinking ...player_1: standplayer_2: 10 of diamondsplayer_2: 3 of spadesplayer_2: thinking ...player_2: hitplayer_2: 3 of diamondsplayer_2: thinking ...player_2: hitplayer_2: king of spadesplayer_2: busted...

Вот как выглядит дерево надзора, когда у нас есть пять одновременных раундов, в каждом по пять игроков:

Заключение

Итак, можем ли мы управлять сложным состоянием в одном процессе? Конечно, можем! Простые функциональные абстракции, такие как Deck and Hand, позволили мне разделить проблемы более сложного состояния раунда без необходимости прибегать к помощи агентов.

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

Если временная логика и/или логика предметной области сложны, рассмотрите возможность их разделения. Подход, который я использовал, позволил мне реализовать более сложное поведение во время выполнения (одновременные уведомления), не усложняя бизнес-процесс раунда. Это разделение также ставит меня в удобное положение, поскольку теперь я могу развивать оба аспекта по отдельности. Добавление поддержки бизнес-концепций дилера, сплита, страхования и других не должно существенно влиять на аспект выполнения. Точно так же поддержка расщеплений сети(netsplits), повторных подключений, сбоев игрока или тайм-аутов не должна требовать изменений в логике домена.

Наконец, стоит помнить о конечной цели. Хотя я туда не ходил (пока), я всегда планировал, что этот код будет размещен на каком-то веб-сервере. Так что некоторые решения принимаются в поддержку этого сценария. В частности, реализация RoundServer, которая принимает модуль обратного вызова для каждого игрока, позволяет мне подключаться к различным типам клиентов, использующим различные технологии. Это делает сервис блэкджека независимым от конкретных библиотек и фреймворков (за исключением стандартных библиотек и OTP, конечно) и делает его полностью гибким.

В этом цикле статей речь идет о параллельном программировании с использованием MPI.

• Часть 1. MPI - Введение и первая программа.

• Часть 2. MPI - Учимся следить за процессами.

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

Номера процессов и общее число процессов

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

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

int MPI_Comm_size(MPI_Comm comm, int* size)

Так что такое коммуникатор и зачем он собственно нужен? Коммуникатор это такой объект, который хранит в себе информацию о запущенных потоках, доступ к которым ему предоставлен. Роль коммуникатора в программе очень важна, так как большая часть работы с процессами связана именно через него, на то он и называется коммуникатором. В MPI существует глобальный коммуникатор который имеет доступ ко всем запущенным потокам, его название MPI_COMM_WORLD. Также мы можем создавать свои, локальные коммуникаторы для выполнения определенных задач на конкретных потоках, и это довольно мило.

Что такое коммуникатор разобрались, теперь было бы неплохо узнать на каком из процессов работает конкретный экземпляр программы. Для этого существует процедура MPI_Comm_size. Она принимает на вход аналогичные параметры, только вместо сохранения количества процессов она сохраняет по адресу номер конкретного процесса. Определена она вот так:

int MPI_comm_rank(MPI_Comm comm, int* rank)

То есть мы передаем ей коммуникатор в котором надо узнать номер процесса и собственно адрес куда его нужно записать.

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

#include <stdio.h>#include "mpi.h"int main(int argc, char **argv){int rank, size;MPI_Init(&argc, &argv);  MPI_Comm_size(MPI_COMM_WORLD, &size);MPI_Comm_rank(MPI_COMM_WORLD, &rank);  MPI_Finalize();  printf("Process: %d, size: %d\n", rank, size);return 0;}

Выход для 5 потоков будет следующим:

Process: 0, size: 5Process: 1, size: 5Process: 2, size: 5Process: 3, size: 5Process: 4, size: 5

Как видим каждый поток напечатал свой номер процесса и общее число запущенных процессов.

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

Работа Comm_size, Comm_rank на примере

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

#include <stdio.h>#include "mpi.h"int main(int argc, char **argv){const int MAX = 20;int rank, size;int n, ibeg, iend;MPI_Init(&argc, &argv);MPI_Comm_size(MPI_COMM_WORLD, &size);MPI_Comm_rank(MPI_COMM_WORLD, &rank);n = (MAX - 1) / size + 1;ibeg = rank * n + 1;iend = (rank + 1) * n;for(int i = ibeg; i <= ((iend > MAX) ? MAX : iend); i++){printf("Process: %d, %d^2=%d\n", rank, i, i*i);}MPI_Finalize();return 0;}

Выход для 5 потоков:

Process: 0, 1^2=1Process: 0, 2^2=4Process: 0, 3^2=9Process: 0, 4^2=16Process: 1, 5^2=25Process: 1, 6^2=36Process: 1, 7^2=49Process: 1, 8^2=64Process: 2, 9^2=81Process: 2, 10^2=100Process: 2, 11^2=121Process: 2, 12^2=144Process: 3, 13^2=169Process: 3, 14^2=196Process: 3, 15^2=225Process: 3, 16^2=256Process: 4, 17^2=289Process: 4, 18^2=324Process: 4, 19^2=361Process: 4, 20^2=400

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

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

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

Работа со временем

Кстати касательно времени. Чтобы работать со временем в MPI можно использовать как стандартные функции из библиотеки <time>, так и процедуры параллельной библиотеки.

double MPI_Wtime(void);double MPI_Wtick(void);

Первая процедура возвращает на вызвавшем ее процессе астрономическое время в секундах, прошедшее с некоторого момента в прошлом. Какой это конкретно момент не совсем имеет значения, но гарантируется, эта точка отсчета не изменится в течение всего времени выполнения программы. Зная эту процедуру можно довольно легко определить время выполнения конкретного участка кода, ведь разность между Wtime в конце и начале программы как раз его и определяет, все стандартно и вполне знакомо.

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

Вторая процедура как раз возвращает разрешение таймера конкретного процесса в секундах.

И на последок покажу как узнать имя физического процессора на котором выполняется программа. Для этого есть процедура MPI_Get_processor_name. Синтаксис и параметры вот такие:

int MPI_Get_Processor_name(char* name, int* len);

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

Резюмируем

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

Для закрепления полученных знаний предлагаю написать вам простую программу, которая узнает является ли число простым для чисел в заданном диапазоне от 1 до N. Это наглядно покажет вам как можно легко и просто распараллелить вычисления с помощью данной технологии и позволит отложить все полученные навыки в голове.

Всем приятного времени суток, хабравчане и те кто набрел на эту статью извне.

В 80 годы прошлого века правительство Японии совершило попытку создать распределенную вычислительную систему следующего поколения с элементами ИИ. Проект закончился достаточно закономерным провалом. Причина провала достаточно проста, почему то посчитали, что простого наличия технологии производства больших интегральных схем хватит для качественного "скачка" в вычислительных технологиях (своеобразный переход количества в качество). Да, история повторилась, после изобретения компьютера, тоже присутствовала необоснованная уверенность в скором появлении ИИ и тоже провалилась.

Сейчас ИИ в основном рассматривается как совокупность нейронов, объединенных в сеть. В свою очередь я попытался посмотреть на человеческий мозг, как на вычислительную систему. При этом не акцентируя внимание на элементах какого типа он базируется.

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Современное состояние вычислительной техники

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

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

Внимание:

Все идеи и алгоритмы, описываемые в данной статье, являются результатом моей независимой и полностью самостоятельной интеллектуальной деятельности. Как автор, разрешаю свободно использовать, изменять, дополнять все идеи и алгоритмы любому человеку или организации в любых типах проектов при обязательном указании моего авторства (Балыбердин Андрей Леонидович Rutel@Mail.ru).

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

Примерное описание идеи в статье : Цифровое бессмертие Инженерный подход.

Определим основные термины

Объект

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

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

Данные

Данные это иерархическая информационная конструкция, состоящая из совокупности символов. Данная структура, описывает физические параметры объекта в настоящем времени и изменяется согласно законам функционирования при взаимодействии с другими объектами.

Символ

Символ представляет собой неделимую информационную конструкцию обладающую свойствами тип и значение, информационная емкость (разрядность, да и вообще дискретность) не оговаривается. Именно через тип символа и происходит связывание виртуального объекта с физическим миром (отражением в физическом мире). В физике есть Международная система единиц измерения, в том числе и через ее отображение в пространство символов происходит отображение физической реальности в виртуальную. Можно сказать, что каждый тип символа это отдельное измерение и каждый виртуальный объект может быть описан через координаты в пространстве измерений.

Взаимодействие объектов

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

Время

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

Вычисление

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

Физическая реализация вычислителя может любой (программа для обычного фон-неймановского процессора, FPGA, обычная логика, нейронные технологии и тд). Каналы переноса данных взаимодействия, по своим свойствам являются обычными каналами связи (точка-точка) с произвольно распределенным по их протяженности FIFO (канал имеет некую информационную емкость). Регулируя скорость передачи символов в отдельных каналах, можно регулировать скорость работы различного ПО, иначе говоря это более эффективный аналог системы приоритетов из парадигмы фон-неймана.

Итог

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

Программирование в новой парадигме превращается из составления списка исполняемых команд (фон-нейман) в описании иерархии законов (свойств), которым должен подчиняться виртуальный объект (или их совокупность). Такой подход открывает очень большие перспективы, например избавляет от неэффективного посредника (программиста) при взаимодействии с вычислительной системой. Разрушает барьер максимальной сложности создаваемой программы. Человек может одновременно оперировать не более чем 5-7 информационными сущностями, что приводит к ошибкам логической связности больших объектов. Программирование в новой парадигме становится инкрементальным, можно постепенно добавлять (редактировать) законы (свойства), до тех пор пока весь объект не станет соответствовать потребностям пользователя. В парадигме фон-неймана такой подход невозможен из-за того что программирование представляет собой создание (редактирование) последовательности действий, которая может полностью измениться при внесении даже небольших изменений в законы функционирования математической модели объекта. Замечу, что нигде не говорится о необходимости изначально понимать устройство создаваемого объекта, можно просто формировать список требований (законов). Произойдет постепенное формирование множества объектов подходящих для решения поставленной задачи. Объекты будут немного отличаться друг от друга, но только в части не значимой для решаемой задачи. Если замкнуть обратную связь с объектом существующим в физической реальности, то можно создать автоматическую исследовательскую систему, которая будет без участия оператора строить виртуальные модели физических объектов. Самое главное, такой подход позволит решить проблему написания адаптивно изменяющегося ПО, предназначенного для работы в не контролируемой среде (в изменяющемся реальном мире).

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

Создание программы по заданным законам функционирования, можно делать многими способами. Самый простой пример : Использовать технологию обучения нейронных сетей, заменив библиотеку примеров на проверку соответствия получаемого объекта заданным законам (свойствам). Более полно технология программирования будет рассматриваться в следующей статье.

Физическая реализация вычислительной системы

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

Сетевая парадигма

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

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

В новой вычислительной системе за счет революционного увеличения эффективности сетевой подсистемы данная проблема должна быть решена. Необходимо получить скорости до 10Е14 бит в секунду для каждого отдельного кристалла, при стабильных задержках задержках передачи, на 90% определяемых скоростью распространения электромагнитной волны в среде передачи. (Подробное описание устройства коммуникационной парадигмы в статье: Синхронный интернет: Синхронная символьная иерархия). Получить такую производительность при использовании медных линий связи практически невозможно, соответственно необходимо полностью изменить подход к проектированию меж-соединений. В настоящее время все компоненты устанавливаются на печатную плату и соединяются медными проводниками. В качестве альтернативы такому подходу, предлагаю в текстолите прокладывать оптические волокна и выводить их с торцов ПП или вырезов в ней для устанавливаемых микросхем. Если сейчас микросхемы распаиваются, то в новом подходе кристаллы могут устанавливаться в прорези в печатной плате. Оптические интерфейсы микросхем должны располагаться с торцов и сопрягаться с оптическими интерфейсами ПП, различные ПП соединять разъемами устанавливаемыми на внешние края плат. Такой подход позволит максимально плотно (значит с минимальными задержками) и надежно строить систему оптических соединений.

Теплоотвод

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

Структура вычислительной системы

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

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

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

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

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Вопросы безопасности

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

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

Возникает вопрос: а если злоумышленник маскируется под легитимного абонента из внешней среды? Канал в новой коммуникационной парадигме является однонаправленным и для обеспечения обратной связи должен содержать маршрут по которому ответ будет доставлен назад злоумышленнику. Обратный маршрут должен быть действующим, иначе данные не будут доставлены. Анализируя этот адрес, коммутатор (или непосредственно объект) может идентифицировать вызывающего абонента, проверить маршрут по которому будут переданы данные ответа и выяснить не выходит ли этот маршрут за пределы доверенной зоны. Соответственно, подменить адрес или прослушать содержимое трафика можно только путем физического присоединения к коммуникационной аппаратуре, находящейся в доверенной зоне и уровень доверия к такому сеансу связи будет равен минимальному уровню доверия к промежуточному участку маршрута (про шифрование трафика пока не говорю). Присоединение к вычислителю на территории пользователя вызовет изменение топологии сетевых соединений, что сразу будет зафиксировано составляющими ее коммутаторами и присоединяемое устройство будет изолировано. Применение объекта с закладками, потребует создание соединения с объектом за пределами зоны в которой находится закладка, максимум что может случиться это хищение данных полученных этим объектом в процессе работы вычислительной системы с дальнейшей передачей собственным каналом связи (внешним по отношению к системе). Для хищения данных, потребуется внедрить закладки или выявить уязвимости, в целой цепочке объектов (от источника данных, до завершения доверенной зоны) Для особо важных частей вычислительной системы, может быть определена полная невозможность соединений не входящих в заранее указанный список и многократное дублирование. Кроме того можно в момент компиляции ПО можно добавить законы маркирующие данные индикатором степени секретности и тогда в коммутаторе можно проверять весь трафик на соответствие степени доверия конкретного канала, степени секретности передаваемой информации (это уже для совсем параноиков).

Границы вычислительной системы

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

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

Энерго-эффективность

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

Вычислитель

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

Далее будет описываться построение вычислителя, с принципами функционирования родственными DataFlow системам, но вычисления объекта возможны и другими вариантами (процессор на принципах фон-неймана, ПЛИС, нейронные сети и др.).

Программа для такого вычислителя представляет собой ациклический направленный граф. Ребра графа, это каналы передачи данных Узлами (вершинами) графа являются операции, которые могут выполнить АЛУ вычислительного ядра.

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

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

Пример структуры данных :

[EXE][READY][KEY][DATA]

EXE данные принадлежат к активному (вычисляемому) пути графа

READY данные вычислены и готовы к дальнейшему использованию (0 нет данных)

KEY уникальный ключ для поиска данных в ассоциативном ЗУ

DATA данные для обработки

Вершина графа вычисляется, только если все входящие ребра имеют значение отличное от нет данных.Если вершины такого графа рассортировать по слоям, таким образом что бы все входящие ребра принадлежали вершинам предыдущих слоев (были вычислены) или были данными состояния объекта. Результатом будет некоторое число групп вершин (слоев), вычислять значения вершин внутри такой группы можно в любом порядке. Но и тут можно немного оптимизировать вычислительный процесс, большинство преобразований (так эффективней для реального АЛУ) имеет один либо два операнда и выдает один результат, все остальные приводят нескольким таким преобразованиям. Максимальная эффективность вычислительного процесса получается когда результат предыдущего преобразования используется как один из операндов в следующем, приходится читать только один операнд и результат не всегда сохранять (он расходуется в следующем преобразовании). Если сделать вторую, уже вертикальную сортировку по этому критерию, то получим набор коротких последовательностей преобразований (нитей). Такие нити могут начинаться и заканчиваться на любом слое.

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Определим механизм чтения второго операнда.

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

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Появляется задача распределения отсортированного графа по отдельным вычислительным ядрам, имеющим некоторый объем памяти, интерфейс связи с соседними ячейками и возможность доступа к каналам связи. Назначим каждому ребру графа уникальный идентификатор, возможно уникальный даже в пределах нескольких объектов. С большой вероятностью число уникальных идентификаторов будет много больше суммарной памяти всех вычислительных ячеек и максимального числа одновременно передаваемых между слоями данных. Поэтому использовать обычную память (данные выбираются по адресу) невыгодно, в новой парадигме в вычислительных ядрах должна использоваться ассоциативная память (замена регистровой и КЭШ памяти в парадигме фон-неймана). АЗУ будет хранить данные до момента их использования и предоставлять их, как своему АЛУ, так некоторому числу соседних, но не всем одинаково быстро (ближайшим соседям быстро за один такт) и это нужно учитывать при размещении нитей по различным ядрам. Получается, что каждое ядро имеет многоканальное АЗУ, число каналов чтения равно числу соседей, которым предоставлен быстрый доступ к данным (остальные медленнее и другим механизмом). Для вычисления объекта необходимо распределить граф по отдельным вычислительным ядрам так, что бы хранимых на каждой ступени (несколько слоев) вычисления данных было не больше числа ячеек АЗУ и список вычисляемых вершин (команд) мог поместиться в память генератора команд (control unit). По вертикали (между слоями) ядра соединяются через основную коммуникационную среду вычислительной системы (обычные каналы передачи данных). Данные из АЗУ, а в ней кроме промежуточных данных хранятся еще и данные состояния объекта, также могут быть коллективно выгружены в оперативную память. Такой механизм можно сравнить с виртуальной памятью в современных процессорах, только здесь это будет механизм виртуального вычислительного пространства. Физически реализованных вычислительных ячеек может быть многократно меньше, чем использовано для исполнения конкретного набора ПО.

<meta http-equiv="CONTENT-TYPE" content="text/html; charset=utf-8"><title></title><meta name="GENERATOR" content="OpenOffice 4.1.6  (Win32)"><style type="text/css"><!--    @page { size: 21cm 29.7cm; margin: 2cm }    P { margin-bottom: 0.21cm }--></style>

Сколько физически существующих ядер необходимо для вычисления конкретного объекта?

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

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

Вычислительный процесс состоит из множества нитей, необходимо синхронизировать (выравнивать) скорость исполнения во всех нитях. В парадигме фон-неймана, без дополнительных и весьма неэффективных ухищрений, это невозможно по причине отсутствия понятия нет данных. В новой парадигме в вычислениях участвуют не просто битовые последовательности, а символы которые кроме непосредственно значения имеют еще и тип. АЗУ при отсутствии требуемого ключа, будет при чтении выдавать символ: нет данных. Вычислительный процесс в каждом ядре идет независимо друг от друга, но в момент когда в ответ на запрос чтения приходит значение нет данных, вычисления останавливается до момента пока не вернется другой тип символа. Таким образом скорость в конкретном ядре притормаживается, относительно всех остальных. Результат вычисления должен быть записан (если это необходимо) в локальное АЗУ, писать можно только в свою локальную часть АЗУ (иначе может случиться клинч). Размер АЗУ конечен и в какой то момент наступит переполнение, после которого необходимо ждать освобождения памяти соседними ядрами (они используют эти данные для вычисления своих вершин). Увеличение размера локального АЗУ позволяет выполнить большее число команд, подготовить больше данных для соседних ядер. Возможность заранее вычислять еще не востребованные данные, является аналогом внеочередного исполнения, в разных ядрах вычислительный процесс может находиться на разных слоях. Если результат вычисления вершины графа используется в нескольких вычислениях, то выгоднее к данным добавить счетчик и уменьшать его при каждом чтении и когда он станет равным нулю освободить ячейку АЗУ, а не занимать отдельные ячейки памяти.

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

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

Проведите мысленный эксперимент:

• Возьмем любую функцию (Изначально созданную на языке высокого уровня).

• Выполним ее и запишем последовательность исполненных ассемблерных команд.

• Для простоты понимания выделим из этих команд только те, которые производят изменения данных, их будет примерно 20% от общего количества.

• Построим граф где вершиной будет команда, ребра будут результатами исполнения или данными имеющимися на момент начала вычисления

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

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

В новой парадигме нет понятие цикла (есть понятие спираль).

Вопрос: Как примирить сегодняшнее представление о программировании, где практически постоянно встречаются различные циклы?

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

Считаем, что цикл имеет бесконечное число повторений. Для того что бы в результате компиляции не получить бесконечного размера граф (программу), необходимо записывать ее в сжатом виде (добавить служебные символы указывающие на бесконечное число повторений) и в момент исполнения распаковывать (control unit) уже в вычислительном ядре. В момент завершения цикла, необходимо отправить сообщение (записать данные в регистр управления) модулю генерирующему последовательность команд сигнал завершающий генерацию повторов тела цикла. В процессе компиляции никто не запрещает выполнить несколько логических итераций цикла за одну физическую, что позволит дополнительно ускорить вычисление. Примерно по той же схеме можно организовывать вызовы функций (процедур), подмену частей графа на оптимизированные варианты (где исключены не использованные пути).

Память в новой парадигме.

Понятие адресного пространства отсутствует и обращение к данным идет по уникальному идентификатору. Никаких ограничений на размер и структуру уникального идентификатора нет, в него можно вложить путь до конкретного запоминающего устройства, тип памяти, параметры доступа и многое другое. Все уникальные идентификаторы могут выглядеть как адрес в сети и при построении маршрута он будет постепенно использоваться промежуточными объектами для маршрутизации, настроек доступа (пароли и др), адреса в физической памяти, размера в битах и многое другое. По существу в процессе доступа к данным уникальный идентификатор является данными взаимодействия. Кроме того большинство обращений к памяти являются коллективными (чтение массивов данных), все отдельные переменные (данные состояния или промежуточные данные) хранятся в АЗУ вычислительного ядра и загружаются (сохраняются) коллективно в момент инициализации вычислительного процесса.

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

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

Настало время обсудить ещё и плохую модель, а также её ключевые отличия от хорошей

Плохая модель классов

Пришло время посмотреть на тип модели классов UML, который можно встретить во множестве проектов. А ещё, увы, который часто поощряется в книгах по UML.

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

Хорошая модель

Здесь у нас та же самая область применения, но совершенно другая модель. Вот что сразу видно:

1. Меньше классов и отношений

2. Более короткие и неполные названия связей

3. Нет ссылочных атрибутов или тегов идентификаторов

4. Менее точные (ориентированные на реализацию) типы данных по атрибутам

Более того, если посмотреть на эти 4 элемента суммарно, будет заметно, что некоторых правил приложения вообще нет, а те, что есть, неправильно сформулированы. Пока поговорим о поверхностных отличиях.

Меньше элементов модели

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

А ещё такая модель будет требовать от программиста (или компилятора) зарезервированного места для заведомо ненужного атрибута. В принципе, это не такая уж проблема, если у вас немного диспетчеров. А если их тысячи? А если мы при этом оставили элементы вида не применимо в большом количестве классов? Для некоторых систем наличие сотен тысяч экземпляров обычное дело, это всего лишь один из вариантов того, как более компактная модель приводит к менее эффективному коду. На практике можно встретить много случаев, когда более детализированная и крупная модель несёт в себе ДНК, которая нужна для более точной реализации правил приложения.

Само собой, у нас тут принцип Чем меньше тем лучше. Но лишь до тех пор, пока это не начинает работать за счет выражения правил. Ведь моделирование в целом процесс аналитический, разбирающий вещи на составляющие. А разработка и реализация это, наоборот, синтез. Разработки моделей, который выполняет объектно-ориентированный анализ, старается выявить и раскрыть все правила приложения. При этом используя столько компонентов, сколько для этого нужно.

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

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

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

Более короткие имена

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

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

Так как имя роли часто совпадает с именем связанного класса, их можно смело удалять, это не уменьшит выразительность модели. Авиадиспетчер и контролер это одно и то же? ОК, так и запишем.

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

Когда аналитик помещает точную глагольную фразу с обеих сторон каждой связи, он вынужден тщательно рассматривать мощность связи и обусловленность с каждой стороны. Это критично именно здесь выражены многие правила. Следует избегать общих, всеохватывающих глагольных фраз, таких как содержит, является группой, имеет и мое любимое связано с. Просто погуглите композиция и агрегация, чтобы понять, насколько легкомысленно использовать общие термины для выражения точных ассоциаций. Какое утверждение скажет вам больше? Блок памяти разбит на взаимоисключающие части |..* Область или блок памяти является (выберите один вариант агрегация / композиция) из области?

Если вы говорите, что диспетчер управляет трафиком внутри <некоторого числа> зон управления, это вынуждает вас подробно рассматривать правила приложения. Вы наверняка уже поняли, что это 0..* и что нулевой случай соответствует выходному диспетчеру. Если перефразировать все в качестве класса дежурный контролер управляет трафиком внутри <некоторого числа> зон управления, то у вас получится отразить множественность 1..* и закрепить важное правило. Перевернув глагольную фразу с активного залога на пассивный, вы получите контрольную зону, в которой содержится трафик, управляемый только одним дежурнымконтроллером. Он должен всегда быть, плюс должен быть на дежурстве в соответствии с правилами приложения. Глагольные фразы ведут модель к повышенной точности.

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

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

Отсутствие тегов идентификаторов или ссылочных атрибутов

В наших примерах выше теги не играют какой-то роли, поэтому подробно на них останавливаться я не буду. Ссылочные атрибуты нужны лишь для того, чтобы показать, что данные на самом деле связаны в табличной форме. Современные компиляторы моделей предполагают существование ссылочных атрибутов и могут управлять ими в фоновом режиме. Тем не менее, существует ряд простых методов, с помощью которых можно распространять и объединять ссылочные атрибуты в рамках нескольких отношений, дабы выразить строгие атрибуты. Я так часто поступаю, поэтому сохраняю ссылочные атрибуты по умолчанию.

Предположим, что каждый экземпляр класса уникален. Автоматически. То есть код сгенерируется так, что каждая строка таблицы соответствует однозначно выбираемой сущности. Поэтому нам не нужно накладывать атрибут{I}на каждый класс. Получается, что если у вас есть какой-то класс под названием Thing, то вы можете дать ему искусственный атрибутThing.ID {I}, но это необязательно это верно только для искусственных идентификаторов.

Однако, все ограничения уникальности реального мира должны быть выражены всегда. Представьте, что вы моделируете взлетно-посадочные полосы с одинаковым курсом и стороной в нескольких аэропортах. У вас не может быть две ВПП с одинаковым курсом и стороной (скажем, два 28R). Это ограничение, и его надо выразить.

Как вы это сделаете?

Вот модель, позволяющая это сделать, если включить ссылочный атрибут в качестве компонента идентификатора.

При помощи тегов{I} и {R}в классе взлетно-посадочной полосы эта модель сообщает нам, что уникальный экземпляр ВПП можно выбрать с помощью подставления заголовка, стороны и кода аэропорта. 28L в SFO, например, это взлетно-посадочная полоса 28 слева в Международном аэропорту Сан-Франциско. Так у вас появляется возможность объединять идентификационные данные и ссылочные теги, чтобы выразить тот или иной факт о реальном мире. А именно несколько взлетно-посадочных полос могут иметь один и тот же курс и сторону, но не в одном аэропорту.

Менее точные типы данных

В хорошей модели мы видели строго определенные типы данных приложения. Плохая же полагается на нечетко определенные типы реализации. Давайте на примере атрибутаControlZone.Name. В хорошей модели он определялся как типCZoneID. На рисунке видно, что имена зон управления состоят изCZи целочисленного значения, например,CZ1,CZ2и прочее в таком духе. Возможно, это получится реализовать и при помощи нечетко определенных типов строк. А если мы в модели говорим, что нам нужна строка, что мы просим в реализации? Если программист (или компилятор) модели работает с более специфичным типом приложения, то сможет при необходимости выбрать более жесткий тип реализации.

Вернемся к модели одного класса. У нас есть тип данных под названиемВысота, это можно определить как количество метров в диапазоне 70 000..-400 с точностью, скажем, 0,01. В отношении данного применения это было бы более точным. Конечно же, программист может захотеть реализовать это в виде данных типа float в C или любого другого типа, который соответствует нужной платформе.

Тут всё сводится к тому же принципу модель должна выражать истинные требования области применения. В максимально сжатом и точном объеме. Без ограничений в плане выбора метода написания кода. Ваша цель сделать модель такой, чтобы она выражала реальные условия области применения максимально сжатым образом. Это пригодится, чтобы расширить реальное применение с учетом возможных будущих требований. Допустим, сегодня модель используют только для самолетов с неподвижным крылом. А завтра захотят добавить еще и вертолеты, и вместо взлетно-посадочных полос у нас будут вертолетные площадки. Значит, есть смысл пересмотреть и самоопределение ВПП и посадочной поверхности.

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

Итак, атрибуты. Даже если мы позволим атрибуту быть свободно определенной строкой (такой как имя), мы сможем использовать типы данных длинное имя и короткое имя. Длинное может быть определено как строка до 80 символов длиной, а короткое до 10. Нацелены они могут быть как на один тип строк реализации, так и на разные.

Поведенческие ограничения в плохой модели не выражены, а вопросы оставлены без ответов

Пора рассмотреть модель в целом поглубже. Что говорит плохая модель о поведении приложения диспетчеров, правильна ли она?

В плохой модели ассоциация контролер равна 1:. Сторона допускает нуль. В итоге мы теряем то тонкое различие междудежурнымдиспетчером, которому не назначена зона управления, ивыходнымдиспетчером.

А вот как выглядит правило R2 в плохой модели: 0..1: 0..1. Эта ни к чему не обязывающая ассоциация охватывает и выходных диспетчеров, которые не вошли в систему, и станции дежурства, которые в данный момент не используются. Вот мы с вами и потеряли ограничение, указывающее, что во время дежурства диспетчер должен быть авторизован в системе.

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

Если диспетчер не курирует какие-либо зоны управления, может ли он при этом быть авторизованным на станции дежурства? И хорошие, и плохие модели позволяют это. И согласно правилам применения, это нормально.

На примере таблицы Самолеты одного класса мы рассмотрели вопросы, на которые могла бы ответить модель. Попробуйте спросить у плохой модели: Какие авиадиспетчеры сейчас не работают?. Она не может ответить на этот вопрос. Она может показать, какие диспетчеры не курируют зоны управления. Но ведь эти диспетчеры могут быть на дежурстве. Можно ли исправить это, добавив атрибут статуса в класс диспетчера в плохой модели? Само собой. Однако при этом вы все равно упускаете диспетчеров со значениемвыходной, которые при этом курируют зону управления.

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

Вот один пример невалидного сценария, разрешенного в плохой модели:

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

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

Актуальные вакансии компанииRetail Rocket

С переводом помогали: Бюро переводовAllcorrect

Редактор: Алексей @Sterhel Якшин

В этом цикле статей речь идет о параллельном программировании с использованием MPI.

• Часть 1. MPI - Введение и первая программа.

• Часть 2. MPI - Учимся следить за процессами.

• Часть 3. MPI - Как процессы обшаются? Сообщения типа точка-точка.

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

Предисловие

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

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

Работает это так: один из процессов, назовем его P1, какого то коммуникатора C должен указать явный номер процесса P2, который также должен быть под коммуникатором С, и с помощью одной из процедур передать ему данные D, но на самом деле не обязательно нужно знать номер процесса, но это мы обсудим далее.

Процедуры в свою очередь разделены на 2 типа: с блокировкой и без блокировки.
1. Процедуры обмена с блокировкой просто останавливают процесс который должен принять сообщение до момента выполнения какого-либо условия.
2. Процедуры без блокировки, как их ещё называют асинхронные, они возвращаются сразу после осуществления коммуникации, немедленно.

Оба типа процедур мы затронем подробно, а пока начнем с процедур с блокировкой.

Передаем и принимаем сообщения

Наконец приступим к практической части. Для передачи сообщений используется процедура MPI_Send. Эта процедура осуществляет передачу сообщения с блокировкой. Синтаксис у нее следующий:

int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest,  int msgtag, MPI_Comm comm);

Что тут есть что:
buf - ссылка на адрес по которому лежат данные, которые мы пересылаем. В случае массивов ссылка на первый элемент.
count - количество элементов в этом массиве, если отправляем просто переменную, то пишем 1.
datatype - тут уже чутка посложнее, у MPI есть свои переопределенные типы данных которые существуют в С++. Их таблицу я приведу чуть дальше.
dest - номер процесса кому отправляем сообщения.
msgtag - ID сообщения (любое целое число)
comm - Коммуникатор в котором находится процесс которому мы отправляем сообщение.

А вот как называются основные стандартные типы данных С++ определенные в MPI_Datatype:

Аналогичным способом указываются и другие типы данных определенные в стандартной библиотеке С/С++ - MPI_[Через _ в верхнем регистре пишем тип так как он назван в С]. Еще один пример для закрепления понимания, есть тип беззнаковых 32 битных целых чисел, назван он uint32_t, чтобы получить этот тип данных переопределенным в MPI необходимо написать следующую конструкцию: MPI_UINT32_T. То есть все вполне логично и легко, верхний регистр, вместо пробелов знаки андерскора и в начале пишем MPI.

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

Теперь поговорим о приеме этих сообщений. Для этого в MPI определена процедура MPI_Recv. Она осуществляет, соответственно, блокирующий прием данных. Синтаксис выглядит вот так:

int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status* status);

Что тут есть что:
buf - ссылка на адрес по которому будут сохранены передаваемые данные.
count - максимальное количество принимаемых элементов.
datatype - тип данных переопределенный в MPI(по аналогии с Send).
source - номер процесса который отправил сообщение.
tag - ID сообщения которое мы принимаем (любое целое число)
comm - Коммуникатор в котором находится процесс от которого получаем сообщение.
status - структура, определенная в MPI которая хранит информацию о пересылке и статус ее завершения.

Тут все практически идентично процедуре Send, только появился аргумент статуса пересылки. Зачем он нужен? Не всегда нужно явно указывать от какого процесса приходит сообщение, какой тег сообщения мы принимаем, чтобы избавиться от неопределенности MPI сохраняет информацию которая не указана в процессе-преемнике явно и мы можем к ней обратиться. Например чтобы узнать процесс который отправил сообщение и тэг этого сообщения:

MPI_Status status;MPI_Recv(&buffer, 1, MPI_Float, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status)tag = status.MPI_SOURCEsource = status.MPI_SOURCE

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

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

Дабы закрепить знания об этих двух процедурах приведу пример как это выглядит на практике, данная программа определяет простые числа на заданном интервале:

#include <stdio.h>#include <time.h>#include "mpi.h"#define RETURN return 0#define FIRST_THREAD 0int* get_interval(int, int, int*);inline void print_simple_range(int, int);void wait(int);int main(int argc, char **argv){// инициализируем необходимые переменныеint thread, thread_size, processor_name_length;int* thread_range, interval;double cpu_time_start, cpu_time_fini;char* processor_name = new char[MPI_MAX_PROCESSOR_NAME * sizeof(char)];MPI_Status status;interval = new int[2];// Инициализируем работу MPIMPI_Init(&argc, &argv);// Получаем имя физического процессораMPI_Get_processor_name(processor_name, &processor_name_length);// Получаем номер конкретного процесса на котором запущена программаMPI_Comm_rank(MPI_COMM_WORLD, &thread);// Получаем количество запущенных процессовMPI_Comm_size(MPI_COMM_WORLD, &thread_size);// Если это первый процесс, то выполняем следующий участок кодаif(thread == FIRST_THREAD){// Выводим информацию о запускеprintf("----- Programm information -----\n");printf(">>> Processor: %s\n", processor_name);printf(">>> Num threads: %d\n", thread_size);printf(">>> Input the interval: ");// Просим пользователья ввести интервал на котором будут вычисленияscanf("%d %d", &interval[0], &interval[1]);// Каждому процессу отправляем полученный интервал с тегом сообщения 0. for (int to_thread = 1; to_thread < thread_size; to_thread++)       MPI_Send(&interval, 2, MPI_INT, to_thread, 0, MPI_COMM_WORLD);// Начинаем считать время выполненияcpu_time_start = MPI_Wtime();}// Если процесс не первый, тогда ожидаем получения данныхelse     MPI_Recv(&interval, 2, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);// Все процессы запрашивают свой интервалrange = get_interval(thread, thread_size, interval);// После чего отправляют полученный интервал в функцию которая производит вычисленияprint_simple_range(range[0], range[1]);// Последний процесс фиксирует время завершения, ожидает 1 секунду и выводит результатif(thread == thread_size - 1){cpu_time_fini = MPI_Wtime();wait(1);printf("CPU Time: %lf ms\n", (cpu_time_fini - cpu_time_start) * 1000);}MPI_Finalize();RETURN;}int* get_interval(int proc, int size, int interval){// Функция для рассчета интервала каждого процессаint* range = new int[2];int interval_size = (interval[1] - interval[0]) / size;range[0] = interval[0] + interval_size * proc;range[1] = interval[0] + interval_size * (proc + 1);range[1] = range[1] == interval[1] - 1 ? interval[1] : range[1];return range;}inline void print_simple_range(int ibeg, int iend){// Прострейшая реализация определения простого числаbool res;for(int i = ibeg; i <= iend; i++){res = true;while(res){res = false;for(int j = 2; j < i; j++) if(i % j == 0) res = true;if(res) break;}res = not res;if(res) printf("Simple value ---> %d\n", i);}}void wait(int seconds) { // Функция ожидающая в течение seconds секундclock_t endwait;endwait = clock () + seconds * CLOCKS_PER_SEC ;while (clock() < endwait) {};}

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

Делаем прием данных более гибким

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

Первая процедура которую мы обсудим следующая:

int MPI_Get_count(MPI_Status* status, MPI_Datatype datatype, int* count);

По структуре status процедура определяет сколько данных типа datatype передано соответствующим сообщением и записывает результат по адресу count.

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

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

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

Хорошо, мы можем принимать на вход какие либо данные и не знать сколько их точно поступает. В таком случае нужно рационально выделять какой-то объем памяти для их сохранения(буферизации). Возникает логичный вопрос о том какой объем выделять, в этом нам поможет процедура MPI_Probe. Она позволяет получить информацию о сообщении которое ожидает в очереди на прием не получая самого сообщения. Синтаксис ее выглядит следующим образом:

int MPI_Probe(int source, int tag, MPI_Comm comm, MPI_Status* status);

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

Теперь на очень простом примере соединим эти процедуры вместе:

#include <iostream>#include "mpi.h"using namespace std;void show_arr(int* arr, int size){for(int i=0; i < size; i++) cout << arr[i] << " ";cout << endl;}int main(int argc, char **argv){int size, rank;MPI_Init(&argc, &argv);MPI_Comm_size(MPI_COMM_WORLD, &size);MPI_Comm_rank(MPI_COMM_WORLD, &rank);if(rank == 0){int* arr = new int[size];for(int i=0; i < size; i++) arr[i] = i;for(int i=1; i < size; i++) MPI_Send(arr, i, MPI_INT, i, 5, MPI_COMM_WORLD);}else{int count;MPI_Status status;MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);MPI_Get_count(&status, MPI_INT, &count);int* buf = new int[count];MPI_Recv(buf, count, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);cout << "Process:" << rank << " || Count: " << count << " || Array: ";show_arr(buf, count);}MPI_Finalize();return 0;}

Что тут происходит?
В данной программе первый процесс создает массив размером равным количеству процессов и заполняет его номерами процессов по очереди. Потом соответствующему процессу он отправляет такое число элементов этого массива, какой номер у этого процесса. Напрмер: процесс 1 получит 1 элемент, процесс 2 получит 2 элемента этого массива и так далее.

Следующие же процессы должны принять это сообщение и для этого смотрят в очередь сообщений, видят это сообщение, собирают информацию в структуру status, после чего получают длину переданного сообщения и создают буфер для его сохранения, после чего просто вы водят то что получили. Для 5 запущенных процессов результат будет вот таким:

Process:1 || Count: 1 || Array: 0 Process:2 || Count: 2 || Array: 0 1 Process:4 || Count: 4 || Array: 0 1 2 3 Process:3 || Count: 3 || Array: 0 1 2 

Собственно 4 результата потому что нулевой процесс занимается отправкой этих сообщений.

И еще несколько типов процедур посылки

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

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

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

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

И еще одна процедура - MPI_Rsend. Она осуществляет передачу сообщения по готовности. Такой процедурой нужно пользоваться аккуратно, так как она требует чтобы процесс-получатель мыл уже готов принять это сообщение. Для того чтобы она выполнилась корректно необходимо заранее позаботиться о синхронизации процессов, либо явно знать, что этот процесс будет находиться в стадии ожидании получения сообщения к моменту вызова Rsend.

Резюме

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

На этом пока все, приятного отдыха хабравчане :)

В этом цикле статей речь идет о параллельном программировании с использованием MPI.

• Часть 1. MPI - Введение и первая программа.

• Часть 2. MPI - Учимся следить за процессами.

• Часть 3. MPI - Как процессы общаются? Сообщения типа точка-точка.

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

Предисловие

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

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

Работает это так: один из процессов, назовем его P1, какого-то коммуникатора C должен указать явный номер процесса P2, который также должен быть под коммуникатором С, и с помощью одной из процедур передать ему данные D, но на самом деле не обязательно нужно знать номер процесса, но это мы обсудим далее.

Процедуры в свою очередь разделены на 2 типа: с блокировкой и без блокировки.
1. Процедуры обмена с блокировкой просто останавливают процесс который должен принять сообщение до момента выполнения какого-либо условия.
2. Процедуры без блокировки, как их ещё называют асинхронные, они возвращаются сразу после осуществления коммуникации, немедленно.

Оба типа процедур мы затронем подробно, а пока начнем с процедур с блокировкой.

Передаем и принимаем сообщения

Наконец приступим к практической части. Для передачи сообщений используется процедура MPI_Send. Эта процедура осуществляет передачу сообщения с блокировкой. Синтаксис у нее следующий:

int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest,  int msgtag, MPI_Comm comm);

Что тут есть что:
buf - ссылка на адрес по которому лежат данные, которые мы пересылаем. В случае массивов ссылка на первый элемент.
count - количество элементов в этом массиве, если отправляем просто переменную, то пишем 1.
datatype - тут уже чутка посложнее, у MPI есть свои переопределенные типы данных которые существуют в С++. Их таблицу я приведу чуть дальше.
dest - номер процесса кому отправляем сообщения.
msgtag - ID сообщения (любое целое число)
comm - Коммуникатор в котором находится процесс которому мы отправляем сообщение.

А вот как называются основные стандартные типы данных С++ определенные в MPI_Datatype:

Аналогичным способом указываются и другие типы данных определенные в стандартной библиотеке С/С++ - MPI_[Через _ в верхнем регистре пишем тип так как он назван в С]. Еще один пример для закрепления понимания, есть тип беззнаковых 32 битных целых чисел, назван он uint32_t, чтобы получить этот тип данных переопределенным в MPI необходимо написать следующую конструкцию: MPI_UINT32_T. То есть все вполне логично и легко, верхний регистр, вместо пробелов знаки андерскора и в начале пишем MPI.

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

Теперь поговорим о приеме этих сообщений. Для этого в MPI определена процедура MPI_Recv. Она осуществляет, соответственно, блокирующий прием данных. Синтаксис выглядит вот так:

int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int source, int tag, MPI_Comm comm, MPI_Status* status);

Что тут есть что:
buf - ссылка на адрес по которому будут сохранены передаваемые данные.
count - максимальное количество принимаемых элементов.
datatype - тип данных переопределенный в MPI(по аналогии с Send).
source - номер процесса который отправил сообщение.
tag - ID сообщения которое мы принимаем (любое целое число)
comm - Коммуникатор в котором находится процесс от которого получаем сообщение.
status - структура, определенная в MPI которая хранит информацию о пересылке и статус ее завершения.

Тут все практически идентично процедуре Send, только появился аргумент статуса пересылки. Зачем он нужен? Не всегда нужно явно указывать от какого процесса приходит сообщение, какой тег сообщения мы принимаем, чтобы избавиться от неопределенности MPI сохраняет информацию которая не указана в процессе-преемнике явно и мы можем к ней обратиться. Например чтобы узнать процесс который отправил сообщение и тэг этого сообщения:

MPI_Status status;MPI_Recv(&buffer, 1, MPI_Float, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status)tag = status.MPI_SOURCEsource = status.MPI_SOURCE

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

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

Дабы закрепить знания об этих двух процедурах приведу пример как это выглядит на практике, данная программа определяет простые числа на заданном интервале:

#include <stdio.h>#include <time.h>#include "mpi.h"#define RETURN return 0#define FIRST_THREAD 0int* get_interval(int, int, int*);inline void print_simple_range(int, int);void wait(int);int main(int argc, char **argv){// инициализируем необходимые переменныеint thread, thread_size, processor_name_length;int* thread_range, interval;double cpu_time_start, cpu_time_fini;char* processor_name = new char[MPI_MAX_PROCESSOR_NAME * sizeof(char)];MPI_Status status;interval = new int[2];// Инициализируем работу MPIMPI_Init(&argc, &argv);// Получаем имя физического процессораMPI_Get_processor_name(processor_name, &processor_name_length);// Получаем номер конкретного процесса на котором запущена программаMPI_Comm_rank(MPI_COMM_WORLD, &thread);// Получаем количество запущенных процессовMPI_Comm_size(MPI_COMM_WORLD, &thread_size);// Если это первый процесс, то выполняем следующий участок кодаif(thread == FIRST_THREAD){// Выводим информацию о запускеprintf("----- Programm information -----\n");printf(">>> Processor: %s\n", processor_name);printf(">>> Num threads: %d\n", thread_size);printf(">>> Input the interval: ");// Просим пользователья ввести интервал на котором будут вычисленияscanf("%d %d", &interval[0], &interval[1]);// Каждому процессу отправляем полученный интервал с тегом сообщения 0. for (int to_thread = 1; to_thread < thread_size; to_thread++)       MPI_Send(&interval, 2, MPI_INT, to_thread, 0, MPI_COMM_WORLD);// Начинаем считать время выполненияcpu_time_start = MPI_Wtime();}// Если процесс не первый, тогда ожидаем получения данныхelse     MPI_Recv(&interval, 2, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);// Все процессы запрашивают свой интервалrange = get_interval(thread, thread_size, interval);// После чего отправляют полученный интервал в функцию которая производит вычисленияprint_simple_range(range[0], range[1]);// Последний процесс фиксирует время завершения, ожидает 1 секунду и выводит результатif(thread == thread_size - 1){cpu_time_fini = MPI_Wtime();wait(1);printf("CPU Time: %lf ms\n", (cpu_time_fini - cpu_time_start) * 1000);}MPI_Finalize();RETURN;}int* get_interval(int proc, int size, int interval){// Функция для рассчета интервала каждого процессаint* range = new int[2];int interval_size = (interval[1] - interval[0]) / size;range[0] = interval[0] + interval_size * proc;range[1] = interval[0] + interval_size * (proc + 1);range[1] = range[1] == interval[1] - 1 ? interval[1] : range[1];return range;}inline void print_simple_range(int ibeg, int iend){// Прострейшая реализация определения простого числаbool res;for(int i = ibeg; i <= iend; i++){res = true;while(res){res = false;for(int j = 2; j < i; j++) if(i % j == 0) res = true;if(res) break;}res = not res;if(res) printf("Simple value ---> %d\n", i);}}void wait(int seconds) { // Функция ожидающая в течение seconds секундclock_t endwait;endwait = clock () + seconds * CLOCKS_PER_SEC ;while (clock() < endwait) {};}

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

Делаем прием данных более гибким

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

Первая процедура которую мы обсудим следующая:

int MPI_Get_count(MPI_Status* status, MPI_Datatype datatype, int* count);

По структуре status процедура определяет сколько данных типа datatype передано соответствующим сообщением и записывает результат по адресу count.

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

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

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

Хорошо, мы можем принимать на вход какие либо данные и не знать сколько их точно поступает. В таком случае нужно рационально выделять какой-то объем памяти для их сохранения(буферизации). Возникает логичный вопрос о том какой объем выделять, в этом нам поможет процедура MPI_Probe. Она позволяет получить информацию о сообщении которое ожидает в очереди на прием не получая самого сообщения. Синтаксис ее выглядит следующим образом:

int MPI_Probe(int source, int tag, MPI_Comm comm, MPI_Status* status);

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

Теперь на очень простом примере соединим эти процедуры вместе:

#include <iostream>#include "mpi.h"using namespace std;void show_arr(int* arr, int size){for(int i=0; i < size; i++) cout << arr[i] << " ";cout << endl;}int main(int argc, char **argv){int size, rank;MPI_Init(&argc, &argv);MPI_Comm_size(MPI_COMM_WORLD, &size);MPI_Comm_rank(MPI_COMM_WORLD, &rank);if(rank == 0){int* arr = new int[size];for(int i=0; i < size; i++) arr[i] = i;for(int i=1; i < size; i++) MPI_Send(arr, i, MPI_INT, i, 5, MPI_COMM_WORLD);}else{int count;MPI_Status status;MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);MPI_Get_count(&status, MPI_INT, &count);int* buf = new int[count];MPI_Recv(buf, count, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status);cout << "Process:" << rank << " || Count: " << count << " || Array: ";show_arr(buf, count);}MPI_Finalize();return 0;}

Что тут происходит?
В данной программе первый процесс создает массив размером равным количеству процессов и заполняет его номерами процессов по очереди. Потом соответствующему процессу он отправляет такое число элементов этого массива, какой номер у этого процесса. Напрмер: процесс 1 получит 1 элемент, процесс 2 получит 2 элемента этого массива и так далее.

Следующие же процессы должны принять это сообщение и для этого смотрят в очередь сообщений, видят это сообщение, собирают информацию в структуру status, после чего получают длину переданного сообщения и создают буфер для его сохранения, после чего просто выводят то, что получили. Для 5 запущенных процессов результат будет вот таким:

Process:1 || Count: 1 || Array: 0 Process:2 || Count: 2 || Array: 0 1 Process:4 || Count: 4 || Array: 0 1 2 3 Process:3 || Count: 3 || Array: 0 1 2 

Собственно 4 результата потому что нулевой процесс занимается отправкой этих сообщений.

И еще несколько типов процедур посылки

Отметим, что вызов и возврат из процедуры MPI_Send далеко не гарантирует того, что сообщение покинуло данный процесс, было получено процессом, которому оно отправлено. Гарантия дается только на то, что мы после этой процедуры можем использовать передаваемые данные в своих целях не опасаясь того, что они как-то изменятся в отправленном сообщении.

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

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

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

И еще одна процедура - MPI_Rsend. Она осуществляет передачу сообщения по готовности. Такой процедурой нужно пользоваться аккуратно, так как она требует чтобы процесс-получатель мыл уже готов принять это сообщение. Для того чтобы она выполнилась корректно необходимо заранее позаботиться о синхронизации процессов, либо явно знать, что этот процесс будет находиться в стадии ожидании получения сообщения к моменту вызова Rsend.

Резюме

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

На этом пока все, приятного отдыха, хабравчане.

Прошло больше года с начала глобальной пандемии, вызванной Covid-19, но жизнь так и не вернулась в прежнее русло. Изменения в рабочих процессах претерпели все без исключения сферы бизнеса. Даже IT, где, вопреки распространенному заблуждению, многие сотрудники посещали офис.

Что произошло в жизни IT компаний за это время, и как карантин повлиял на digital-маркетинг? Перемены не ограничились переходом на удаленную работу - они гораздо глубже и серьезнее.

Выигрывает тот, кто умеет адаптироваться

Не секрет, что IT-индустрия практически не потерпела убытков во время пандемии. Наоборот, спрос на онлайн-сервисы и технологии вырос. Многие процессы перешли из обычной жизни в Интернет: покупка одежды и еды, общение с коллегами и родственниками, развлечения и игры. Люди оказались запертыми в своих домах, им пришлось получать привычные услуги непривычным способом, а бизнесу - подстраиваться.

Как следствие, вырос спрос на такие IT проекты и направления как:

• Онлайн-продажи.

• Продвижение бизнеса в онлайн-медиа и соцсетях.

• Реклама и digital-маркетинг.

• Разработка мобильных приложений для ресторанов и магазинов.

• Финансовые технологии, криптовалюты и DeFi (Decentralised Finance).

• Игры, стриминг, подписки на онлайн ТВ и все, что связано с развлечениями.

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

Реклама - по-прежнему двигатель прогресса

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

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

Еще одна реформа digital-маркетинга коснулась формата рекламы. Среди аудитории стали востребованы:

• Короткие видео (Instagram, Tik-Tok);

• Стримы;

• Реклама от блогеров и инфлюенсеров;

• Блог-посты и кейсы;

• Посты в соцсетях.

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

Так ли легко IT-специалистам?

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

Общение в Telegram и совещания по Zoom не в новинку для IT-специалистов - им легко освоить пару приложений. Однако постоянная работа из дома негативно сказалась на их продуктивности, дисциплине, скорости и эффективности коммуникации с коллегами. Стоит упомянуть, что у многих элементарно не получается сосредоточиться на заданиях, когда члены семьи круглосуточно находятся рядом.

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

Впрочем, у перехода на удаленку есть и неоспоримые плюсы:

• Экономия времени и денег на проезд до и от работы.

• Больше времени с семьей.

• Возможность работать из любой точки мира (что актуально при открытии границ).

• Меньше усилий на поддержание внешнего вида.

• Снижение риска инфекции.

• Гибкий график и возможность подработок.

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

Да и стоит ли?

Что случилось с вакансиями?

IT-сфера была, пожалуй, самой подготовленной к новым реалиям, которые связаны с коронавирусной инфекцией и переездом в домашний офис.

С апреля месяца 2020 года значительно увеличился спрос на специалистов по обработке больших данных, по ведению цифрового документооборота, а также на digital-специальности. Так же возросло количество IT-специалистов, которые находятся в поиске работы, на 30% относительно марта 2019 года.

Работа из дома - мечта или наказание?

На этот вопрос нет однозначного ответа, но года пандемии хватило, чтобы каждый взвесил все За и Против. Некоторым сотрудникам не терпится вернуться в офис, однако большинство успели оценить преимущества работы из дома и теперь согласны лишь на удаленку. Возможно, секрет кроется в организации рабочего пространства?

Очень важно обустроить свой мини-офис, если вы вынуждены работать дома. Для этого фрилансеры рекомендуют:

1. Выделить отдельную комнату или зону, где будет располагаться техника и рабочее место.

2. Настроить освещение и создать приличный фон (на случай важных переговоров).

3. Договориться с домочадцами, чтобы вам не мешали в рабочее время.

4. Избавиться от всего, что отвлекает. Порядок на рабочем месте - порядок в голове.

5. Заранее решить вопрос с перекусами и обедами (заказать доставку или приготовить в свободное время).

Ко всему можно привыкнуть, и удаленная работа не исключение. Но готовы ли компании к таким переменам?

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

Вывод

Пандемия существенно повлияла на рабочие процессы во всех компаниях, включая IT-индустрию. Далеко не всем удаленная работа пришлась по нраву: тем, кто не способен к самодисциплине в домашних условиях или живет в окружении большой семьи и маленьких детей, хотелось вернуться в офис. Но, к счастью, большинство работников в IT-индустрии все же смогли адаптироваться к новым условиям без ущерба производительности. А это значит, что многие компании безвозвратно уйдут в онлайн.