并行编程和计算

Question

2. 假设存在一个魔术方块，Sherlock Holmes在其中按顺序复制了反向字母字符串的输出。后来，他将这个魔术方块作为输入输入到在通用并行计算机上运行的并行程序中，使得前三行中的一个字符由于某些错误而被擦除。借助基于并行功能的基础硬件，（并行）程序再次将修改后的输出排列到反向字母列表中（相对于其余15个字符），以便将擦除的字符推入该字符的最后一个框。魔方。

（a）这是并行程序使用的方法。（b）在使用给定反向字母字符串的示例的帮助下进行解释。

Answer 1

关于一个纯粹的[SERIAL] Sherlock HOLMES配备了魔法的[[PARALLEL]的故事，但_（有点）“瑕疵”沃森...

The initial state:

        anOrderedListOfCHARs   "abcdefghijklmnop"
        (indices)           :  ////////////////
                              0123456789ABCDEF

                              0    1    2    3
                               \    \    \    \     
        aMagicSQUARE:           [_]  [_]  [_]  [_]

                                [_]  [_]  [_]  [_]

                                [_]  [_]  [_]  [_]

                                [_]  [_]  [_]  [_]
                                   \    \    \    \
                                    C    D    E    F  

---

下一个？

Sir Holmes, a "detective", has
                used [SERIAL]-process,
                putting one CHAR
                after another,
                in a reversed order,
                to produce this:

        aMagicSQUARE (indices)  [F]  [E]  [D]  [C]
                      reverse'd                         
                                [B]  [A]  [9]  [8]

                                [7]  [6]  [5]  [4]

                                [3]  [2]  [1]  [0]

---

下一个？

A [PARALLEL]-machine a "defective" one
                has damaged the
                state, somewhere
                in row 1, 2 or 3

                we do not know where
                we do yet know it was just one and only a one CHAR

        aMagicSQUARE (indices)   
                one & only one  [?]  [?]  [?]  [?]
                cell in R1:R3    
                has a single    [?]  [?]  [?]  [?]
                defect (EMPTY)   
                                [?]  [?]  [?]  [?]

                                [d]  [c]  [b]  [a]

---

下一个？

A [PARALLEL]-machine can first      ___________________________________
       [PARALLEL]-map cells        /    /    /    /                   /
                 back into      [F]  [E]  [D]  [C]                   /
                 a vector-like      ______________________________  /
                 list              /    /    /    /              / /
                                [B]  [A]  [9]  [8]              / /
                                    _________________________  / /
                                   /    /    /    /         / / /
                                [7]  [6]  [5]  [4]         / / /
                                    ____________________  / / /
                                   /    /    /    /    / / / /
                                [3]  [2]  [1]  [0]    / / / /
                                                     / / / /  
                                      0123__________/ / / /
                                     ////4567________/ / /
                                    ////////89AB______/ /
                                   ////////////CDEF____/
                                  ////////////////  
                                "abcdefghijklmnop"
                                ////////////////
                               0123456789ABCDEF

---

现在呢？

Given the "defective" step,
           we expect not more
           than a one defect,
           so now we get this:
                                "????????????mnop"
                                ////////////////
                               0123456789ABCDEF

---

所以？

Next step is a [PARALLEL]-test
        for a single (empty)
        a one & only one
        index we can STORE
        it is a collision-free

           _aDefectCellINDEX_:      3  
                                    |
                                "abc^efghijklmnop"
                                ////////////////
                               0123456789ABCDEF

---

下一个？

Next step is a [PARALLEL]-shuffle
        for all cells
        since a single found defect
        it has to be orchestrated
        as a [PARALLEL]-READ,
        but a block/stride-safe
        ordered (as destructive)        ________________
        [PARALLEL]-WRITE               /               /
        for all cells "after"         3               /
        _aDefectCellINDEX_            ^456789ABCDEF  /
        and placing (EMPTY)          ^////////////  /
        "defect" to the last    "abc^efghijklmnop" /
        position in the list        ////////////  /
                               "abcefghijklmnop^"/
                                              /_/

---

Depending on the actual HARDWARE,
        the [PARALLEL]-machine
        may prefer to BLOCK-READ
                   to BLOCK-ERASE
                  and BLOCK-SHIFT/WRITE
        not to handle a single exception
                     (a defect) alone in a "divergent"-code-path

---

小学，亲爱的沃森，对吗？