tjazerzen/parallelisation-of-graph-algorithms-in-functional-programming-languages

V okviru diplomske naloge bom raziskoval paralelizacijo grafovskih algoritmov v funkcijskih programskih jezikih.

parallelisation-of-graph-algorithms-in-functional-programming-languages's Issues

Napaka `Stdlib.Effect.Unhandled(Domainslib__Task.Wait(_, _))` pri uporabi Domainslib za paralelizacijo dijkstre

Pozdravljeni,

Pri implementaciji paralelnega algoritma Dijkstre v OCaml z uporabo knjižnice Domainslib sem naletel na težavo. Ko poskušam izvesti paralelno nalogo z uporabo T.parallel_for v funkciji parallel v modulu Dijkstra, se nederministrično pojavi napaka Stdlib.Effect.Unhandled(Domainslib__Task.Wait(_, _)). To je moja spisana metoda:

parallelisation-of-graph-algorithms-in-functional-programming-languages/playground/graph/dijkstra.ml

Lines 123 to 153 in ddc1533

	let parallel (graph : WeightedGraph.t) start_node end_node =
	let rec loop pq visited =
	if pq = PQ.empty () then raise Not_found
	else
	let current_cost, current_node, pq = PQ.extract pq in
	let new_visited = current_node :: visited in
	if current_node = end_node then (current_cost, new_visited)
	else
	let neighbours =
	WeightedGraph.edges graph |> NodeMap.find current_node
	|> NodeMap.bindings
	in
	let pool =
	T.setup_pool ~num_domains:(List.length neighbours - 1) ()
	in
	let new_pq = ref pq in
	(* let mutex = Mutex.create () in *)
	T.parallel_for pool ~start:0
	~finish:(List.length neighbours - 1)
	~body:(fun i ->
	(* Mutex.lock mutex; *)
	let neighbor, weight = List.nth neighbours i in
	if List.mem neighbor new_visited then ()
	else new_pq := PQ.insert neighbor (current_cost +. weight) pq
	(* Mutex.unlock mutex; *));
	T.teardown_pool pool;
	loop !new_pq new_visited
	in
	let pq_start = PQ.empty () |> PQ.insert start_node 0.0 in
	let cost, path = loop pq_start [] in
	(cost, List.rev path)

Razumem, da se ta napaka pojavi, ker program ni "thread-safe", sprašujem pa se, zakaj program ni thread-safe. Uporabljam namreč nespremenljivo vrsto s prednostjo:

parallelisation-of-graph-algorithms-in-functional-programming-languages/playground/graph/dijkstra.ml

Lines 8 to 91 in ddc1533

	module PQ : sig
	type elt
	(** The type of elements stored in the priority queue. *)
	type t
	(** The type [t] represents a priority queue, which is used in Dijkstra's algorithm to keep track of the nodes to visit next. *)
	exception Queue_is_empty
	(** [Queue_is_empty] is raised when attempting to remove an element from an empty priority queue. *)
	val empty : unit -> t
	(** [empty ()] returns an empty priority queue. *)
	val insert : Node.t -> priority -> t -> t
	(** [insert new_node new_priority pq] returns a new priority queue [pq'] with [new_node] inserted with priority [new_priority]. *)
	val remove_top : t -> t
	(** [remove_top pq] returns a new priority queue [pq'] with the lowest priority element removed. Raises [Queue_is_empty] if [pq] is empty. *)
	val extract : t -> priority * Node.t * t
	(** [extract pq] returns a tuple of the priority, node, and priority queue of the lowest priority element in [pq]. Raises [Queue_is_empty] if [pq] is empty. *)
	end = struct
	type priority = float
	type elt = Empty | PQNode of priority * Node.t * elt * elt
	type t = { priority_queue : elt; mutex : Mutex.t }
	exception Queue_is_empty
	let empty () = { priority_queue = Empty; mutex = Mutex.create () }
	let insert (new_node : Node.t) (new_priority : priority) (pq : t) : t =
	Mutex.lock pq.mutex;
	let rec insert_aux new_node new_priority queue =
	match queue with
	| Empty -> PQNode (new_priority, new_node, Empty, Empty)
	| PQNode (existing_priority, existing_node, left, right) ->
	if new_priority <= existing_priority then
	PQNode
	( new_priority,
	new_node,
	insert_aux existing_node existing_priority right,
	left )
	else
	PQNode
	( existing_priority,
	existing_node,
	insert_aux new_node new_priority right,
	left )
	in
	let updated_priority_queue =
	insert_aux new_node new_priority pq.priority_queue
	in
	Mutex.unlock pq.mutex;
	{ pq with priority_queue = updated_priority_queue }
	let remove_top (pq : t) =
	let rec remove_top_aux priority_queue =
	match priority_queue with
	| Empty -> raise Queue_is_empty
	| PQNode (_, _, left, Empty) -> left
	| PQNode (_, _, Empty, right) -> right
	| PQNode
	( _,
	_,
	(PQNode (left_priority, left_node, _, _) as left),
	(PQNode (right_priority, right_node, _, _) as right) ) ->
	if left_priority <= right_priority then
	PQNode (left_priority, left_node, remove_top_aux left, right)
	else PQNode (right_priority, right_node, left, remove_top_aux right)
	in
	{ pq with priority_queue = remove_top_aux pq.priority_queue }
	let extract (pq : t) =
	Mutex.lock pq.mutex;
	let extract_aux priority_queue =
	match priority_queue with
	| Empty -> raise Queue_is_empty
	| PQNode (priority, elt, _, _) as queue ->
	(priority, elt, remove_top { pq with priority_queue = queue })
	in
	let priority, extracted_node, updated_pq = extract_aux pq.priority_queue in
	Mutex.unlock pq.mutex;
	(priority, extracted_node, updated_pq)
	end

Implementirana vrsta s prednostjo nam še dodatno preko Mutex-ev (https://v2.ocaml.org/manual/parallelism.html#s:par_sync) zagotavlja, da več niti ne more hkrati spreminjati istega mesta v pomnilniku.

Zavedam se, da na tem mestu:

parallelisation-of-graph-algorithms-in-functional-programming-languages/playground/graph/dijkstra.ml

Line 138 in ddc1533

let new_pq = ref pq in

uporabljam reference, ki sicer so v osnovni spremenljive, vendar referencirajo nespremenljivo podatkovno strukturo. Po drugi strani pa nimam idej, kako bi ta program lahko paraleliziral brez uporabljene reference.

Imate mogoče kak predlog, kako bi to lahko razrešil?

Kako predstaviti graf v OCamlu

OCaml nima slovarjev kot Python. Možnost je, da seznam sosednosti predstavim kot:

• OCamlov hash map
• BST z (ključ, vrednost), kjer je vrednost še en BST z seznamom sosedov tega ključa.