A series of theoretical and programming assignments (mini-projects - MP's): Each MP must be passed with at least 50% points.
Final grading: 50% - 59% E, 60% - 69% D, 70% - 79% C, 80% - 89% B, 90% -100% A.
Máte zapnutý náhled celé osnovy, zpět na běžné zobrazení.
Načítání a prohlížení osnovy může být v závislosti na množství obsahu pomalejší.
The course introduces elementary concepts of parallel programming, the parallel computing model PRAM and a basic set of platform-independent parallel programming techniques. The second part of the course is devoted to practical multi-thread programming, including individual projects.
A series of theoretical and programming assignments (mini-projects - MP's): Each MP must be passed with at least 50% points.
Final grading: 50% - 59% E, 60% - 69% D, 70% - 79% C, 80% - 89% B, 90% -100% A.
Vaším úkolem je:
Až to budete mít hotové tak to otestujte následovně:
Unlike the example of simple parallel insertion in our textbook, here we do not need to add all new leaves to an existing node of the 2-3 tree at once, but each thread may compete for lock of the parent node to add its leaf and eventually balance the parent if needed. See the example of three new leaves B1, B2, B3 being added to the tree:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; using System.Threading.Tasks; namespace _23treeNew { // Třída Node obsahuje základní metody pro práci s uzelm 2-3 stromu class Node { Listchildren; // privátní seznam potomků public Node parent { get; private set; } // rodičovský uzel public int key { get; private set; } // max. klíč v podstromu tohoto uzlu /* Neudržujeme hodnoty l,m,r přímo v uzlu. Získáme je jako children[0].key, children[1].key, children[2].key */ public Node(int value) { key = value; children = new List (); } public int NoOfChildren => children.Count; // Vrátí potomka na pozici idx, počítáno od nuly // Případnou výjimku neřešíme public Node Child(int idx) => children[idx]; // Přidá nového potomka a zatřídí ho do seznamu podle jeho klíče public void AddChild(Node node) { node.parent = this; var position = children.FindIndex(child => node.key <= child.key); position = position < 0 ? children.Count : position; children.Insert(position, node); UpdateKey(); } // Odstraní potomka na pozici idx, počítáno od nuly // Případnou výjimku neřešíme public void RemoveChild(int idx) { children.RemoveAt(idx); UpdateKey(); } // Přepočítá klíč, nutno volat vždy, když se něco změnilo u potomků public void UpdateKey() { if (children.Any()) key = children.Max(child => child.key); } // True pokud uzel je listem public bool isLeaf() { return !children.Any(); } }
// Tato třída bude obsahovat veškeré potřebné metody ke vkládání uzlů do stromu class Tree23 { Node root; // Konstruktor vytváří strom sestávající z kořene public Tree23() { root = new Node(int.MaxValue); } // vrací list s nejmenším klíčem, který je aspoň tak velký jako// pokud takový klíč ve stromu není, vrací nejpravější list public Node Search(int key) { return Search(root, key); } // vrací list podstromu s nejmenším klíčem, který je aspoň tak velký jako // pokud takový klíč v podstromu není, vrací nejpravější list Node Search(Node node, int key) { if (node.isLeaf()) return node; int i = 0; while (i < node.NoOfChildren - 1 && key > node.Child(i).key) i++; return Search(node.Child(i), key); } // vloží do stromu nový list s klíčem key a případně strom vyváží // vrací false, pokud klíč už ve stromě je public bool Insert(int key) { var leaf = Search(key); if (leaf.key == key) return false; var newLeaf = new Node(key); // Nový uzel se má přidat k rodiči nalezeného listu // Pokud nalezený list nemá rodiče, znamená to, že strom sestává pouze z kořene // Pak tedy přidáváme nový uzel jako potomka kořene var parent = leaf.parent ?? leaf; // Bude-li tuto metodu volat více vláken, musíte nyní zamknout . // Pokud se to nepovede, čekáte na odemčení. // Pak ale musíte znovu získat , protože se mezitím mohl změnit! // Jiné vlákno mohlo vyvažovat a přepojit na jiného rodiče. // Pokus o zamčení se tedy musí dělat v cyklu while - DOPLŇTE ZDE parent.AddChild(newLeaf); // Metoda Balance postupuje stromem vzhůru a vyvažuje postupně vyšší uzly. // Vyvažovaný uzel vždy zamkne (zámky jsou reentrantní) a pak odemkne. Balance(parent); return true; } // Metoda vrací textový výpis celého stromu v jednotlivých řádcích pod sebou public override string ToString() { var level = new List { root }; var result = ""; while (level.Any()) { var lowerLevel = new List (); // Nodes of different parents will be separated by | var parent = level[0].parent; foreach (var node in level) { result += (node.parent == parent ? "" : "| ") + (node.key == int.MaxValue ? "+N" : node.key.ToString()) + " (" + node.NoOfChildren + ") "; parent = node.parent; for (int i = 0; i < node.NoOfChildren; i++) lowerLevel.Add(node.Child(i)); } result += "\n"; level = lowerLevel; } return result; } } }
1. fáze: každý prvek bi zařazovaného pole B[1..k] bude mít své vlákno, které ho zatřídí do stromu metodou Search (viz vzorový kód). Výsledkem bude pomocné pole C[1..k], obsahující pro každý prvek bi odkaz na list stromu, vlevo od něhož se má bi připojit.
2. fáze: potřebujeme nyní identifikovat všechny neprázdné řetězce B1, ..., Bm (jejich počet m předem neznáme), které se budou vkládat mezi listy stávajícího stromu. Na obr. 6.6 ve skriptech to vypadá jednoduše, ale uvědomte si, že algoritmus ty řetězce "nevidí." Musíme mu sdělit, kde v poli B začínají a končí. Začátek každého řetězce zjistíme jednoduše v poli C - je to pozice, jejíž obsah je odlišný od pozice předchozí. Sekvenčně by to byla hračka, ale my to musíme paralelizovat.
Proto vytvoříme pomocné binární pole D[1..k] s jedničkami na počátečních pozicích řetězců:
D[1]: = 1
for 2 ≤ i ≤ k pardo
if C[i -1] ≠ C[i] then D[i] := 1
else D[i] := 0
Následně spočteme prefixovou sumu pole D a výsledek uložíme do pole E. V prvcích pole E nyní máme očíslování jednotlivých řetězců B1, ..., Bm. Všimněte si, že jejich počet je m = E[k]. Konečně vytvoříme pole F[1..m+1], které bude obsahovat indexy začátků řetězců Bi v poli B:
F[1] := 1
for 2 ≤ i ≤ k pardo
if E[i -1] ≠ E[i] then F[E[i]] := i
F[m+1] := k+1
Každý řetězec Bi začíná na pozici F[i] a končí na pozici F[i+1]-1. Příklad pro k = 8, m = 4:
C:
a1 | a2 | a2 | a2 | a5 | a5 | a9 | a9 |
D:
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
E:
1 | 2 | 2 | 2 | 3 | 3 | 4 | 4 |
F:
1 | 2 | 5 | 7 | 9 |
3. fáze: pro každý řetězec Bi se spustí samostatné vlákno, které ho bude zařazovat. Zamkne rodičovský uzel p listu ai , k němuž se Bi připojuje, a přidá k němu prostřední prvek Bi jako nový list. Pro každé ze dvou zbývajících neprázdných půlek Bi spustí samostatné vlákno, které se bude chovat analogicky, viz obr. 6.6 ve skriptech. Nyní se spustí metoda Balance, kterou lze myslím použít beze změny z jednoduché verze algoritmu. Stejně tak zamykání a odemykání rodičovského uzlu.
Oproti skriptům je implementace zjednodušená, není nutno synchronizovat jednotlivé vlny vyvážení stoupající stromem, stačí vždy zamknout a vyvážit jen uzel, ke kterému se navěšuje nový potomek.