并行算法：均匀划分（PSRS）和方根划分（SIMD-CREW）

àì夳堔傛蜴生んèń 2023-07-17 07:18 19阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neXVuZmVpeHl6_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neXVuZmVpeHl6_size_16_color_FFFFFF_t_70 1][]

例子：均匀划分技术进行数据的并行排序（N=27,p=3）
    
    (a)均匀划分（p1,p2,p3）
    22,21,9,87,3,5,18,34,68|70,12,24,7,23,65,89,1,3|43,15,6,16,17,45,67,98,66
    (b)局部排序
    3,5,9,18,21,22,34,68,87|1,3,7,12,23,24,65,70,89|6,15,16,17,43,45,66,67,98
    (c)正则采样
    3    18    34        1    12    65        6    17    66
    (d)采样排序
    1,3,6,12,17,18,34,65,66
    (e)选择主元（p-1个）
    12,34
    (f)主元划分
    P1: 3,5,9|18,21,22,34|68,87
    P2: 1,3,7,12|23,24|65,70,89
    P3: 6|15,16,17|43,45,66,67,98
    (g)全局交换
    3,5,9,1,3,7,12,15,16,17|18,21,22,34,23,24,15,16,17|68,87,65,70,89,43,45,66,67,98
    (h)归并排序
    1,3,3,5,7,9,12,15,16,17|15,16,17,18,21,22,23,24,34|43,45,65,66,67,68,70,87,89,98

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neXVuZmVpeHl6_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neXVuZmVpeHl6_size_16_color_FFFFFF_t_70 3][]

例子：请使用划分设计技术中的方根划分技术进行数据的并行排序。数据自拟
    A={1,3,8,14,16,26,37,45},n=8
    B={2,4,7,9,12,19,25,34,42,44,49,50} m=12
    (1)、方根划分
    A划分1~2段，B划分1~3段
    A:1,3,8*,14,16,26*,37,45
    B:2,4,7*,9,12,19*,25,34,42*,44,49,50
    (2)、段间比较
    A1主元8*落在B1段，A2主元26*落在B3段
    (3)、段内比较
    A1主元8*插入到B1：2,4,7,8*
    A2的主元26*插入到B3:25,26*,34,42
    (4)、递归归并
    此时:
    A1{1,3},A2{14,16},A3{37,45}
    B1{2,4,7,8},B2{9,12,19},B3{25,26,34,42},B3{44,49,50}
    对A1和B1重复（1）-（3）步骤：
    a、方根划分：
    A1:1，3*->A11:{1,3*}
    B1：2,4*,7,8*->B11:{2,4*},B12:{7,8*}
    b、段间比较
    A11主元3*落在B11
    c 、段内比较
    A11插入B11中  B11:2,3,4
    最后，同理把A1都并入B1中  B1：{1,2,3,4}
    自此完成A1到B1的归并。
    其他段同理。最终归并后：
    B:1,2,3,4,7,8,9,12,14,16,19,25,26,34,37,42,44,45,49,50

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neXVuZmVpeHl6_size_16_color_FFFFFF_t_70]: /images/20230528/a4e88ab024034bcb9132f3a06cb9fcb4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neXVuZmVpeHl6_size_16_color_FFFFFF_t_70 1]: /images/20230528/ab24d48d715841fd89593dde44935aba.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neXVuZmVpeHl6_size_16_color_FFFFFF_t_70 2]: /images/20230528/b7435ede90f9436aa83a643cf7f4694a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5neXVuZmVpeHl6_size_16_color_FFFFFF_t_70 3]: /images/20230528/1d609d52b68045018aadfb4cfcdab164.png