9

DPH を使用して nqueens の問題を実装しようとしましたが、最終的に GHC.Prim.Int# をベクトル化できませんというエラーが発生しました。エラーをグーグルで調べたところ、パターンマッチングに使用されるリテラルのベクトル化について話している GHC バグが見つかりました (http://haskell.1045720.n5.nabble.com/GHC-5702-Can-t-vectorise-pattern-matching-on -numeric-literals-td5076659.html)。これが同じバグかどうかはわかりません。私のコードは次のとおりです。

{-# LANGUAGE ParallelArrays #-}
{-# OPTIONS_GHC -fvectorise #-}
module NQueensP (nqueens_wrapper) 
where

import qualified Prelude
import Data.Array.Parallel
import Data.Array.Parallel.Prelude
import Data.Array.Parallel.Prelude.Int as I
import qualified Data.Array.Parallel.PArray as P


isSafe i q n  = isSafeHelper i (Prelude.zip (P.toList (toPArrayP q)) [n, n I.- 1..1]) 
            where isSafeHelper i []  = True
                  isSafeHelper i (x:xs) = (i I.== Prelude.fst x) && I.abs(i I.-   
                                  (Prelude.fst x)) I./= I.abs(n I.- (Prelude.snd x)) && 
                                       isSafeHelper i xs

nqueens_wrapper::Int -> PArray (PArray Int)
nqueens_wrapper n = toPArrayP (mapP toPArrayP (nqueens n 0))

nqueens::Int -> Int -> [:[:Int:]:]
nqueens n 1 = [:[:i:] | i <- (enumFromToP 1 n) :]
nqueens n k = [: [:i:] +:+ q | i <- oneton, q <- boards, isSafe i q k:]
           where boards = nqueens n (k I.- 1)
                 oneton = (enumFromToP 1 n)

何か間違ったことをしている場合はお知らせください。GHC 7.4.1 を使用しています。

前もって感謝します。

4

1 に答える 1

1

はい、これはあなたが言及したバグに関連しているようです。表示されるエラーは、次の行に起因します。

nqueens n 1 = [:[:i:] | i <- (enumFromToP 1 n) :]

どうやら、n-パターンを-fvectorise有効にして使用することはできません。この行を手動で脱糖して、n-パターンを削除しましょう。

nqueens n w | w I.== 1 = [:[:i:] | i <- (enumFromToP 1 n) :]

ここまでで、不可解なエラー メッセージを 1 つ処理しました。次のエラー メッセージも同様に不可解に見えるため、これで作業が完了したわけではありません。

*** Vectorisation error ***
    Tycon not vectorised:  []

（私が思うに）の問題isSafeは、でコンパイルされていない多くのデータ型と変数を使用していることです-fvectorise。これは、モジュール内でこれらの構造を再定義しない限り、連結リスト ( Tycon not vectorised: [])、Prelude.fst、Prelude.snd、またはをそのまま使用できないことを意味します。Prelude.zip(面倒なことに、再定義しないと使えません(.)。)

書き直す必要がありisSafeます。その最初の行を見てみましょう。

isSafe i q n  = isSafeHelper i (Prelude.zip (P.toList (toPArrayP q)) [n, n I.- 1..1])

は使用できませんがPrelude.zip、代わりに を使用できます。zipPつまり、変換する必要はqもうありません。ただし、減少リストは DPH コンビネータを使用して書き直す必要があります。ばかばかしいことに、enumFromThenToPは存在しないので、代わりに、mapP (n I.-) (enumFromToP 0 (n I.- 1))の並列等価物を取得すると言います[n, n I.- 1..1]。したがって、この行は次のようになります。

isSafe i q n  = isSafeHelper i (zipP q (mapP (n I.-) (enumFromToP 0 (n I.- 1))))

今ではisSafeHelper：

isSafeHelper i [] = True
isSafeHelper i (x:xs)
    = (i I.== Prelude.fst x)
    && I.abs(i I.- (Prelude.fst x)) I./= I.abs(n I.- (Prelude.snd x))
    && isSafeHelper i xs

Prelude.fstとPrelude.sndが利用できないため、パターン自体でタプルのこれらの部分を抽出するだけでこれを修正できます。

isSafeHelper i [] = True
isSafeHelper i ((x1,x2):xs)
    = (i I.== x1)
    && I.abs(i I.- x) I./= I.abs(n I.- x2)
    && isSafeHelper i xs

しかし、もちろん、それでもコンパイルされません。引数は、Prelude スタイルの連結リストではなく、並列リストになります。これに対処するために、 function を使用して、より機能的なスタイルでこれを書き直しますall。

isSafeHelper i xs = all (isSafePredicate i) xs

isSafePredicate i (x1,x2)
    = (i I.== x1)
    && I.abs(i I.- x) I./= I.abs(n I.- x2)

allリンクされたリストでも機能しますが、独自の関数でリストを手動で分解していないことに注意してください。allPfor parallel リストがあればいいと思いませんか? あるでしょうが、ありません。ただし、それを書くのは難しくありません。

allP :: (a -> Bool) -> [: a :] -> Bool
allP p arr = andP (mapP p arr)

以上をまとめると、isSafe以下のように書けます。

isSafe i q n = allP (isSafePredicate i n) (zipP q ntoone) 
  where
    isSafePredicate i n (x1, x2)
        = (i I.== x1)
        && I.abs(i I.- x1) I./= I.abs(n I.- x2)
    ntoone = mapP (n I.-) (enumFromToP 0 (n I.- 1))

nqueens_wrapperそのままでいいようです。コードがコンパイルされるはずです。

いくつかのメモ:

  • それが機能するかどうかはわかりませんが (*** Exception: crossMapP: not implementedが表示され、修正方法がわかりません)、動作するはずです。
  • 逆に書き直しisSafeてもうまくいきません。Preludeリスト内の数値を操作しようとするPreludeと、再び苦情が発生Int#します。isSafeこれは、が少なくとも 1 つのベクトル化された関数で使用されているためだと思いますnqueens。

  • を含めないでくださいData.Array.Parallel.Prelude。モジュールの説明には次のように書かれています。

    このモジュールは、ユーザー コードに明示的にインポートしないでください。ユーザー コードは Parallel のみをインポートし、ベクトライザーが型クラスをサポートするまでは型固有のモジュールをインポートする必要があります。

  • ローカル定義に夢中にならないでください。お使いのバージョンには引数isSafeHelperがありません。n

于 2012-12-29T22:48:25.900 に答える