녹에서 평행 한 나무를 처리하기

Question

나는 병렬로 처리하고 싶은 녹의 나무 구조를 가지고있다. 내 진짜 문제는 더 복잡하다, 그러나 이것은 내가 지금이 기본적으로 직렬 버전입니다 :

이

#[derive(Debug)] 
enum BinaryTree { 
    Node(Box<BinaryTree>, Box<BinaryTree>), 
    Leaf(i32), 
} 

use BinaryTree::*; 

impl BinaryTree { 
    /// Applies the given function to every leaf in the tree 
    fn map<F: Fn(i32) -> i32>(&mut self, f: &F) { 
     match *self { 
      Node(ref mut tree1, ref mut tree2) => { 
       tree1.map(f); 
       tree2.map(f); 
      } 
      Leaf(ref mut n) => *n = f(*n), 
     } 
    } 
} 

내가 사용하지 않는이 병렬화 싶습니다

• 없음 잠금
• 스레드 풀을, 또는 그렇지 않으면 다시 만들 스레드에 있지 않는
는
• (바람직하게는) 안전하지 않은 코드

문제는 매우 자연스러운 t 보인다 병렬화 : 모든 노드에서 각 하위 노드를 동시에 처리하여 잠재적으로 직렬 버전으로 폴백 할 수 있습니다. 그러나 표준 라이브러리에 아직없는 범위가 지정된 스레드가 필요합니다. 나는 scoped-pool 상자에 대한 정착하고,이 솔루션에 도착 :

extern crate scoped_pool; 

impl BinaryTree { 
/// Applies the given function to every leaf in the tree 
    fn map_parallel<F>(&mut self, f: &F, scope: &scoped_pool::Scope) 
     where F: Fn(i32) -> i32 + Send + Sync 
    { 
     match self { 
      &mut Node(ref mut tree1, ref mut tree2) => { 
       // Create new, smaller scope 
       scope.zoom(|scope2| { 
        // Concurrently process child nodes 
        scope2.recurse(|scope3| { 
         tree1.map_parallel(f, scope3); 
        }); 
        scope2.recurse(|scope3| { 
         tree2.map_parallel(f, scope3); 
        }); 
       } 
          );}, 
      &mut Leaf(ref mut n) => *n = f(*n), 
     } 
    } 
} 
fn main() { 
    let mut tree = Node(
     Box::new(Node(
      Box::new(Node(
       Box::new(Node(
        Box::new(Node(
         Box::new(Leaf(11)), 
         Box::new(Leaf(15)))), 
        Box::new(Leaf(13)))), 
       Box::new(Leaf(19)))), 
      Box::new(Leaf(5)))), 
     Box::new(Leaf(10))); 

    let thread_pool = scoped_pool::Pool::new(4); 
    tree.map_parallel(&|n| n + 1, &scoped_pool::Scope::forever(thread_pool)); 
    println!("{:?}", tree); 
} 

그러나이 교착 상태에 갇혀 얻을 나타나고, 그 이유를 이해하지 않습니다. Rust에서 병렬로 나무를 처리하는 관용적 인 방법은 무엇입니까?

Answer 1

교착 상태에

및 묶어 종료하기 전에 자신을 map_parallel를 호출하는 스레드를, 묶어하는 당신은 4 개 스레드를

가 다음 번 map_parallel 부르는 이유 이해가 안 돼요 스레드, 등등. 스레드가 종료되기 전에 스레드가 부족합니다. 이 예제에서는 5 개의 스레드로 전환하여 교착 상태를 "수정"합니다. 당연히 트리 깊이에 따라 스레드 수를 변경하는 것이 이상적이지 않습니다.

---

별도의 문제로 코드를 분할하는 것이 좋습니다. 이미 병렬로 처리하고 있으므로 각 노드는 서로 독립적이어야합니다. 이는 반복자를 구현할 수 있다는 것을 의미합니다.

impl BinaryTree { 
    fn iter_mut(&mut self) -> IterMut { 
     IterMut { queue: vec![self] } 
    } 
} 

struct IterMut<'a> { 
    queue: Vec<&'a mut BinaryTree>, 
} 

impl<'a> Iterator for IterMut<'a> { 
    type Item = &'a mut i32; 

    fn next(&mut self) -> Option<Self::Item> { 
     match self.queue.pop() { 
      Some(tree) => { 
       match *tree { 
        Leaf(ref mut n) => Some(n), 
        Node(ref mut left, ref mut right) => { 
         self.queue.push(right); 
         self.queue.push(left); 
         self.next() // bad recursive, see note 
        } 
       } 
      } 
      None => None, 
     } 
    } 
} 

이것은 데이터 구조로 스레딩 라이브러리의 모든 얽힘을 제거하기 때문에 좋습니다. 이와 함께, 당신은 그 단일 스레드 돌연변이를 수행하도록 선택할 수 있습니다

for node in tree.iter_mut() { 
    *node += 1; 
} 

또는 스레드를 :

let thread_pool = scoped_pool::Pool::new(2); 
thread_pool.scoped(|scope| { 
    for node in tree.iter_mut() { 
     scope.execute(move || { 
      *node += 1; 
     }) 
    } 
}); 

---

당신은 내가 반복자에 꼬리 재귀 코드를 사용하는 것을 알게 될 것이다. Rust는 이것을 최적화하지 않으므로이를 반드시 명령형으로 변경해야합니다.

이터레이터에 대해 zipper을 사용하여 조사 할 수도 있습니다.