Типы вычислений.
Лет пять назад товарищи из Беркли разразились программной статьёй под названием "Ландшат параллельных вычислений: вид из Беркли". В ней приводятся 13 "карликов" - типичных шаблонов вычислений (стр. 19(.
Среди всего прочего, там есть и задачи, которые не могут быть массивно-параллельными или для которых сделать параллельный алгоритм затруднительно (считалось на тот момент). В качестве примера приведу разреженную линейную алгебру, комбинационную логику и машины состояний.
Разреженная линейная алгебра интересна плохой масштабируемостью по данным. Упакованные форматы (compressed sparse row/column) приводят к хранению на одном вычислителе большого количества данных. Пример: социальный сети имеют граф связей типа "богатый богатеет", где количество связей обратно пропорционально частоте встречания. В таком графе есть узлы, связанные практически со всеми. Как ни записывайте матрицу связности такого графа, всё равно будет столбец или строка, размер которой пропорционален количеству узлов в графе. Для больших графов такой столбец или строка может превыщать размеры памяти на одной машине кластера. Или, если памяти хватило, какая-то машина будет слишком занята работой.
Однако, если хранить матрицу в виде случайных подматриц в виде упорядоченных массивов троек (i,j,значение), то всё становится значительно интересней. Куча статей, как сделать разреженную линейную алгебру масштабируемой. Перемножение матриц в виде упорядоченных подматриц-массивов имеет временную сложность чуть ли не линейную от количества ненулевых элементов в результирующей матрице. Поскольку подматрицы можно выбирать случайно, нет проблем с балансировкой данных.
В примерах комбинационной логики есть алгоритмы, которые параллелизовать тяхело. Шифрование с CBC, например, не параллельно вообще никак. А вот вычисление криптосумм вполне себе параллельно: MD6.
И последнее - машины состояний. Многие задачи из этого раздела сводятся к синтаксическому разбору, от декодирования кодов Хаффмана, до... декодирования MPEG потоков. Для синтаксического разбора также известен параллельный алгоритм: Cocke-Younger-Kasami (CYK) алгоритм.
При уменьшении параллелизма длина конвейера процессора начинает определять скорость выполнения. Чем короче длина, тем лучше. Что напоминает мне о тенденции сокращения тактовых частот.
Среди всего прочего, там есть и задачи, которые не могут быть массивно-параллельными или для которых сделать параллельный алгоритм затруднительно (считалось на тот момент). В качестве примера приведу разреженную линейную алгебру, комбинационную логику и машины состояний.
Разреженная линейная алгебра интересна плохой масштабируемостью по данным. Упакованные форматы (compressed sparse row/column) приводят к хранению на одном вычислителе большого количества данных. Пример: социальный сети имеют граф связей типа "богатый богатеет", где количество связей обратно пропорционально частоте встречания. В таком графе есть узлы, связанные практически со всеми. Как ни записывайте матрицу связности такого графа, всё равно будет столбец или строка, размер которой пропорционален количеству узлов в графе. Для больших графов такой столбец или строка может превыщать размеры памяти на одной машине кластера. Или, если памяти хватило, какая-то машина будет слишком занята работой.
Однако, если хранить матрицу в виде случайных подматриц в виде упорядоченных массивов троек (i,j,значение), то всё становится значительно интересней. Куча статей, как сделать разреженную линейную алгебру масштабируемой. Перемножение матриц в виде упорядоченных подматриц-массивов имеет временную сложность чуть ли не линейную от количества ненулевых элементов в результирующей матрице. Поскольку подматрицы можно выбирать случайно, нет проблем с балансировкой данных.
В примерах комбинационной логики есть алгоритмы, которые параллелизовать тяхело. Шифрование с CBC, например, не параллельно вообще никак. А вот вычисление криптосумм вполне себе параллельно: MD6.
И последнее - машины состояний. Многие задачи из этого раздела сводятся к синтаксическому разбору, от декодирования кодов Хаффмана, до... декодирования MPEG потоков. Для синтаксического разбора также известен параллельный алгоритм: Cocke-Younger-Kasami (CYK) алгоритм.
При уменьшении параллелизма длина конвейера процессора начинает определять скорость выполнения. Чем короче длина, тем лучше. Что напоминает мне о тенденции сокращения тактовых частот.