Лекция: Массивы; представление многомерных массивов при помощи векторов Айлифа

Массивы бывают разные: одномерные и многомерные J

Что как минимум мы можем о них знать? Размер ячейки, адреса(в том числе нулевого элемента), границы.

Так же знаем языки без структур данных — Fortran 77 и классический BASIC.

Массив структур → несколько массивов.

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

Хранение многомерных массивов. Например, в семействе С(ях) левый индекс старший, а вот в Фортране – правый.

Так же многомерные массивы мы можем представлять через вектор Айлифа (это такой дядя из далекого 1961 года).

Для тех, кто не в теме. Вектор Ilife (массив ссылок на массивы) – это структура данных, используемая для реализации многомерных массивов. Вектор ilife для n-мерного массива состоит из вектора указателей на (n-1)-мерный массив. Они часто используются, чтобы избежать потребности в дорогих операциях по умножению, выполняя вычисление адреса на элементе массива. Они могут также использоваться, чтобы реализовывать треугольные массивы или другие виды массивов непонятной формы. Вектор ilife для 2-мерных массивов просто вектор указателей на вектора данных, т.е. вектор ilife представляется в виде столбцов массива, где каждый столбец указатель на вектор-строку.

Из современных ЯВУ используются в C (int** или int*[], но не int[][N]), Java, Perl, Python, Ruby.

В Java массив — всегда ссылочный тип, в Pascal —контейнерный. В C и C♯ — по-разному, в Perl, Python, Ruby —массивов, как таковых, нет, вместо них списки.

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

Ну и обобщение на тему массивов.

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

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

Ох…… начнем с элементарных вещей про распараллеливание….

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

Основная проблема в том, что поднять мощность одного процессора в n раз очень непросто.

Вообще, параллелизм круто делать в следующих задачах:

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

· Уровень программ. Части одной задачи выполняются на множестве процессоров. Достигается на параллельных ВС.

· Уровень команд. Выполнение команды разделяется на фазы, а фазы нескольких последовательных команд м.б. перекрыты за счет конвейеризации. Достижим на ВС с одним процессором.

· Уровень битов (арифметический уровень). Биты слова обрабатываются одновременно. Реализуется в обычных и суперскалярных процессорах.

Что требуется от языков для параллелизма? Обычные языки: с использованием библиотек параллельной обработки данных; С использованием параллельных расширений; Специализированные параллельные языки; Обычные языки с естественной поддержкой параллельности.

Понятное дело, известные топологии параллелизма: Шина, Кольцо, Плоскость, Цилиндр, Тор, M динамических линий между N процессорами, Гиперкуб, Топологии, имитирующие физику задач.

Показатели некоторые (включая Ускорение и Эффективность):

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

Этот закон иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей.

Здесь ускорение, которое может быть получено на вычислительной системе из n процессоров, по сравнению с однопроцессорным решением не будет превышать величины S.

А, тут еще затронута тема оптимизации умножения квадратных матриц. Ну. Ок. Читаем. Курим.

Есть такой алгоритм Штрассена, который дает выигрыш при умножении больших матриц (от 64).

Он решают проблему за Θ(nlog27),а обычное умножение за время Θ(n³) = Θ(nlog28). Так то.

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

Пример, конечно же.

Пусть A, B — две квадратные матрицы над кольцом R. Матрица C получается по формуле:

Разделим матрицы A, B и C на равные по размеру блочные матрицы

где

тогда

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

Теперь определим новые элементы

которые затем используются для выражения Ci, j. Таким образом, нам нужно всего 7 умножений на каждом этапе рекурсии. Элементы матрицы C выражаются из Pk по формулам

Итерационный процесс продолжается n раз, до тех пор пока матрицы Ci, j не выродятся в числа (элементы кольца R). На практике итерации останавливают при размере матриц от 32 до 128 и далее используют обычный метод умножения матриц. Это делают из-за того, что алгоритм Штрассена теряет эффективность по сравнению с обычным на малых матрицах из-за дополнительных копирований массивов.

Поразрядная сортировка (Цифровая сортировка) — алгоритм сортировки за линейное время.

Алгоритм сортировки.
Числа сортируются по разрядам. Существует два варианта least significant digit (LSD) и most significant digit (MSD). При LSD сортировке, сначала сортируются младшие разряды, затем старшие. При MSD сортировке все наоборот. При LSD сортировке получается следующий порядок: короткие ключи идут раньше длинных, ключи одного размера сортируются по алфавиту, это совпадает с нормальным представлением чисел: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При MSD сортировке получается алфавитный порядок, который подходит для сортировки строк. Например «b, c, d, e, f, g, h, i, j, ba» отсортируется как «b, ba, c, d, e, f, g, h, i, j». Если MSD применить к числам разной длины, то получим последовательность 1, 10, 2, 3, 4, 5, 6, 7, 8, 9.

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

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

Еще существует блочная сортировка(Bucket Sort). Идея заключается в следующем:

Распределяем по блокам

Сортируем блоки (можно параллельно и распределённо)

Сливаем
Как и QuickSort, можно затормозить специально подобранными данными.

Ну и напоследок поведаю я Вам о Map-Reduce
Map-Reduce – модель распределенных вычислений, представленная компанией гугл, используемая для параллельных вычислений над очень большими, в несколько петабайт, наборами данных в компьютерных кластерах.
Работа MapReduce состоит из двух шагов: Map и Reduce.

На Map-шаге происходит предварительная обработка входных данных. Для этого один из компьютеров (называемый главным узлом — master node) получает входные данные задачи, разделяет их на части и передает другим компьютерам (рабочим узлам — worker node) для предварительной обработки. Название данный шаг получил от одноименной функции высшего порядка.

На Reduce-шаге происходит свёртка предварительно обработанных данных. Главный узел получает ответы от рабочих узлов и на их основе формирует результат — решение задачи, которая изначально формулировалась.
Дмитрий Вадимович приводил пример с собой и своей женой:
Два человека берут стаканы с деньгами, выбирают монетки и сортируют на кучки с одним достоинством (map).
Считается количество в каждой кучке и, таким образом, её достоинство (reduce1).

Суммируются достоинства кучек монет: сперва для одного человека (reduce2), потом общее (reduce3).