Computing черепахи с параллельным алгоритмом

Question

Вопрос заключается в

«Пусть заданы н-элемент массив (θ, d) кортежей, которые представляют собой последовательность команд к черепахе первого поворота & thetas градусов против часовой стрелки а затем двигать вперед d единиц. Опишите параллельный алгоритм с использованием контекстов параллельного сканирования и/или параллельного префикса сканирования, чтобы вычислить конечное местоположение черепахи в O (n/p + log p) времени в p-процессорной системе ».

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

Answer 1

Нам нужно расширить область ввода, чтобы мы могли определить оператор ассоциативной композиции. Для этой проблемы стандартным выбором является представление движения черепахи как матрицы, которая отображает локальные координаты черепахи [x y 1] в глобальные координаты [x' y' 1] (3D-координаты с дополнительным 1, потому что я использую homogeneous coordinates).

[x y 1] [a b 0] 
     [c d 0] = [x' y' 1] 
     [e f 1] 

Для пары (θ, d), мы получим матрицу

[ cos θ  sin θ 0] 
[ -sin θ  cos θ 0] 
[d cos θ d sin θ 1]. 

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