dph-examples: closest pairs
authorAmos Robinson <amos.robinson@gmail.com>
Fri, 9 Nov 2012 07:03:05 +0000 (18:03 +1100)
committerAmos Robinson <amos.robinson@gmail.com>
Fri, 9 Nov 2012 07:03:05 +0000 (18:03 +1100)
dph-examples/dph-examples.cabal
dph-examples/dph-examples.template
dph-examples/examples/spectral/ClosestPairs/dph/Main.hs [new file with mode: 0644]
dph-examples/examples/spectral/ClosestPairs/dph/Vector.hs [new file with mode: 0644]
dph-examples/examples/spectral/ClosestPairs/dph/Vector1.hs [new file with mode: 0644]
dph-examples/examples/spectral/ClosestPairs/dph/Vectorised.hs [new file with mode: 0644]
dph-examples/examples/spectral/ClosestPairs/dph/Vectorised1.hs [new file with mode: 0644]

index 67d9e6d..5849b7b 100644 (file)
-
-
-Name:                dph-examples
-Version:             0.8.0.1
-License:             BSD3
-License-file:        LICENSE
-Author:              The DPH Team
-Maintainer:          Ben Lippmeier <benl@ouroborus.net>
-Build-Type:          Simple
-Cabal-Version:       >=1.8
-Stability:           experimental
-Category:            Data Structures
-Homepage:            http://www.haskell.org/haskellwiki/GHC/Data_Parallel_Haskell
-Description:         Data Parallel Haskell example programs.
-Synopsis:            Data Parallel Haskell example programs.
+Name: dph-examples
+Version: 0.8.0.1
+License: BSD3
+License-file: LICENSE
+Author: The DPH Team
+Maintainer: Ben Lippmeier <benl@ouroborus.net>
+Build-Type: Simple
+Cabal-Version: >=1.8
+Stability: experimental
+Category: Data Structures
+Homepage: http:
+Description: Data Parallel Haskell example programs.
+Synopsis: Data Parallel Haskell example programs.
 
 -- Smoke ----------------------------------------------------------------------
 -- examples/smoke/data
 Executable dph-smoke-bool
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vectorised
   hs-source-dirs: examples/smoke/data/Bool
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 -- examples/smoke/prims
 Executable dph-smoke-concat
-  build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  main-is:        Main.hs
-  other-modules:  Vectorised
+  build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  main-is: Main.hs
+  other-modules: Vectorised
   hs-source-dirs: examples/smoke/prims/Concat
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 Executable dph-smoke-sumsq
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vector
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vector
                   Vectorised
                   Timing Randomish
   hs-source-dirs: examples/smoke/prims/SumSquares/dph lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+
+
 Executable dph-smoke-evens
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vector
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vector
                   Vectorised
                   Timing Randomish
   hs-source-dirs: examples/smoke/prims/Evens/dph lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 -- examples/smoke/sharing
 Executable dph-smoke-indices
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised Vector
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vectorised Vector
   hs-source-dirs: examples/smoke/sharing/Indices lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+
+
 Executable dph-smoke-rank
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised Util Timing Randomish
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vectorised Util Timing Randomish
   hs-source-dirs: examples/smoke/sharing/Rank lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 Executable dph-smoke-reverse
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised Vector Randomish
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vectorised Vector Randomish
   hs-source-dirs: examples/smoke/sharing/Reverse lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 -- Imaginary ------------------------------------------------------------------
 -- Executable dph-imaginary-primes
---   Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
---   Main-is:        Main.hs
---   other-modules:  Vectorised
---   hs-source-dirs: examples/imaginary/Primes lib
---   ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+-- Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+-- Main-is: Main.hs
+-- other-modules: Vectorised
+-- hs-source-dirs: examples/imaginary/Primes lib
+-- ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 Executable dph-imaginary-words
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vectorised
   hs-source-dirs: examples/imaginary/Words lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 -- Spectral -------------------------------------------------------------------
+Executable dph-spectral-closestpairs
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vector
+                  Vector1
+                  Vectorised1
+                  Timing
+                  Points2D.Types
+  hs-source-dirs: examples/spectral/ClosestPairs/dph lib
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+
 Executable dph-spectral-dotp
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vector
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vector
                   Vectorised
                   Timing Randomish
   hs-source-dirs: examples/spectral/DotProduct/dph lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 Executable dph-spectral-smvm
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vectorised
                   Vector
                   Timing
   hs-source-dirs: examples/spectral/SMVM/dph lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 Executable dph-spectral-quickhull
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vectorised
                   Timing Points2D.Types SVG
   hs-source-dirs: examples/spectral/QuickHull/dph examples/spectral/QuickHull/lib lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 Executable dph-spectral-quickhull-vector
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  QuickHullIO
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: QuickHullIO
                   QuickHullSplit
                   QuickHullVector
                   Timing Points2D.Types SVG
   hs-source-dirs: examples/spectral/QuickHull/vector examples/spectral/QuickHull/lib lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 Executable dph-spectral-quicksort
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised
+  Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+  Main-is: Main.hs
+  other-modules: Vectorised
                   Timing
   hs-source-dirs: examples/spectral/QuickSort/dph lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
-
-
-Executable dph-spectral-quickselect
-  Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.6.*, dph-prim-par == 0.6.*, dph-lifted-vseg == 0.6.*, HUnit == 1.2.*
-  Main-is:        Main.hs
-  other-modules:  Vectorised
-                  Vector
-                  Timing
-  hs-source-dirs: examples/spectral/QuickSelect/dph lib
-  ghc-options:    -eventlog -rtsopts -threaded -fllvm -Odph -package dph-lifted-vseg -fcpr-off -fno-liberate-case -fsimpl-tick-factor=1000
+  ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 
 -- Real -----------------------------------------------------------------------
 --Executable dph-real-nbody-gloss
---    Main-is:        MainGloss.hs
---    other-modules:  Common.Dump Common.World Common.Body Common.Util 
---                     Solver Solver.ListBH.Solver
---                            Solver.NestedBH.Solver
---                            Solver.VectorBH.Solver
---                            Solver.VectorNaive.Solver
---                     Timing Points2D.Types Points2D.Generate
---                     System.Console.ParseArgs
---                     Gloss.MainArgs Gloss.Draw Gloss.Config
---    Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*, gloss == 1.6.*
---    hs-source-dirs: examples/real/NBody examples/real/NBody/Gloss lib
---    ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
+-- Main-is: MainGloss.hs
+-- other-modules: Common.Dump Common.World Common.Body Common.Util
+-- Solver Solver.ListBH.Solver
+-- Solver.NestedBH.Solver
+-- Solver.VectorBH.Solver
+-- Solver.VectorNaive.Solver
+-- Timing Points2D.Types Points2D.Generate
+-- System.Console.ParseArgs
+-- Gloss.MainArgs Gloss.Draw Gloss.Config
+-- Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*, gloss == 1.6.*
+-- hs-source-dirs: examples/real/NBody examples/real/NBody/Gloss lib
+-- ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
 
 Executable dph-real-nbody
-    Main-is:        MainBatch.hs
-    other-modules:  Common.Dump Common.World Common.Body Common.Util 
+    Main-is: MainBatch.hs
+    other-modules: Common.Dump Common.World Common.Body Common.Util
                     Solver Solver.ListBH.Solver
                            Solver.NestedBH.Solver
                            Solver.VectorBH.Solver
                            Solver.VectorNaive.Solver
                     Timing Points2D.Types Points2D.Generate
                     Batch.MainArgs Batch.Config
-    Build-depends:  base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
+    Build-depends: base == 4.6.*, vector == 0.9.*, random == 1.0.*, old-time == 1.1.*, containers == 0.5.*, dph-base == 0.8.*, dph-prim-par == 0.8.*, dph-lifted-vseg == 0.8.*, HUnit == 1.2.*, repa-flow == 3.2.*
     hs-source-dirs: examples/real/NBody examples/real/NBody/Batch lib
-    ghc-options:    -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
-
+    ghc-options: -eventlog -rtsopts -threaded -fllvm -optlo-O3 -Odph -package dph-lifted-vseg -fcpr-off -fsimpl-tick-factor=1000
index c8bb2f5..70a7de2 100644 (file)
@@ -93,6 +93,17 @@ Executable dph-imaginary-words
 
 
 -- Spectral -------------------------------------------------------------------
+Executable dph-spectral-closestpairs
+  Build-depends:  DPH_DEPENDS
+  Main-is:        Main.hs
+  other-modules:  Vector
+                  Vector1
+                  Vectorised1
+                  Timing
+                  Points2D.Types
+  hs-source-dirs: examples/spectral/ClosestPairs/dph lib
+  ghc-options:    DPH_OPTIONS
+
 Executable dph-spectral-dotp
   Build-depends:  DPH_DEPENDS
   Main-is:        Main.hs
diff --git a/dph-examples/examples/spectral/ClosestPairs/dph/Main.hs b/dph-examples/examples/spectral/ClosestPairs/dph/Main.hs
new file mode 100644 (file)
index 0000000..446af5e
--- /dev/null
@@ -0,0 +1,104 @@
+
+import Vector
+-- import Vectorised
+import Vector1
+import Vectorised1
+import Timing
+import Points2D.Generate
+import Points2D.Types
+import System.Environment
+import Data.Array.Parallel.PArray      as P
+
+main :: IO ()
+main 
+ = do  args    <- getArgs
+       case args of
+         [alg,pointCount]      
+           -> run alg (read pointCount)
+
+         _ -> do
+               putStr usage
+               return ()
+
+
+-- | Command line usage information.
+usage :: String
+usage  = unlines
+       [ "Usage: closestpairs <vector|vectorised|vector1|vectorised1> <points>"        ]
+
+
+-- | Run the benchmark.
+run    :: String
+        -> Int                         -- ^ How many points to use.
+       -> IO ()
+       
+{-
+run "vectorised" pointCount
+ = do
+       vPoints <- pointsPArrayOfUArray
+               $ genPointsDisc pointCount (400, 400) 350 
+
+       -- Force points to create the input vector.
+       vPoints `seq` return ()
+
+       -- Compute the convex hull.
+       (pair, tElapsed)
+               <- time 
+               $  let  pair    = closestPA vPoints
+                  in   pair `seq` return pair
+                                       
+       -- Print how long it took.
+       putStr $ prettyTime tElapsed
+-}
+
+run "vector" pointCount
+ = do
+       let vPoints     = genPointsDisc pointCount (400, 400) 350 
+
+       -- Force points to create the input vector.
+       vPoints `seq` return ()
+
+       -- Compute the convex hull.
+       (pair, tElapsed)
+               <- time 
+               $  let  pair    = closestV vPoints
+                  in   pair `seq` return pair
+                                       
+       -- Print how long it took.
+       putStr $ prettyTime tElapsed
+
+
+run "vectorised1" pointCount
+ = do
+       vPoints <- pointsPArrayOfUArray
+               $ genPointsDisc pointCount (400, 400) 350 
+
+       -- Force points to create the input vector.
+       vPoints `seq` return ()
+
+       -- Compute the convex hull.
+       (pair, tElapsed)
+               <- time 
+               $  let  pair    = closest1PA vPoints
+                  in   pair `seq` return pair
+                                       
+       -- Print how long it took.
+       putStr $ prettyTime tElapsed
+
+run "vector1" pointCount
+ = do
+       let vPoints     = genPointsDisc pointCount (400, 400) 350 
+
+       -- Force points to create the input vector.
+       vPoints `seq` return ()
+
+       -- Compute the convex hull.
+       (pair, tElapsed)
+               <- time 
+               $  let  pair    = closest1V vPoints
+                  in   pair `seq` return pair
+                                       
+       -- Print how long it took.
+       putStr $ prettyTime tElapsed
+
+
diff --git a/dph-examples/examples/spectral/ClosestPairs/dph/Vector.hs b/dph-examples/examples/spectral/ClosestPairs/dph/Vector.hs
new file mode 100644 (file)
index 0000000..65feb5b
--- /dev/null
@@ -0,0 +1,109 @@
+{-# LANGUAGE BangPatterns #-}
+module Vector (closestV, closeststupidV) where
+import Points2D.Types
+import qualified Data.Vector            as V
+import qualified Data.Vector.Unboxed    as U
+
+-- removed the sqrt here - only some users actually need it
+distance :: Point -> Point -> Double
+distance (x1, y1) (x2, y2)
+  = ( (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) )
+
+-- Distance between two points, but return a very large number if they're the same...
+distancex :: Point -> Point -> Double
+distancex a b
+ = let d = distance a b
+   in  if d == 0 then 1e100 else d
+
+
+-- An n^2 algorithm for finding closest pairs.
+-- Our divide and conquer drops back to this once there are few enough points
+closeststupid :: U.Vector Point -> U.Vector (Point,Point)
+closeststupid pts
+ = U.map m1 pts
+ where
+  m1 a = (a, U.minimumBy (m2 a) pts)
+  m2 a b c = distancex a b `compare` distancex a c
+
+
+near_boundary :: U.Vector (Point,Point) -> Double -> Double -> U.Vector (Int,(Point,Point))
+near_boundary a x0 d
+ = U.filter check (U.indexed a)
+ where
+  check (_,((x1,_),_)) = abs (x1 - x0) < d
+
+
+new_nearest :: U.Vector (Int,(Point,Point)) -> U.Vector (Int,(Point,Point)) -> U.Vector (Int,(Point,Point))
+new_nearest a b
+ | U.length b == 0 = a
+ | otherwise
+ = let bp = U.map (\(_,(pt1,_)) -> pt1) b
+   in  U.map (m1 bp) a
+ where
+  m1 bp (k,(pt1,pt2))
+   = let pn = U.minimumBy (\b c -> distancex pt1 b `compare` distancex pt1 c) bp
+     in  (k, (pt1, check pt1 pn pt2))
+  check pt1 pn pt2
+   = if   distancex pt1 pn < distancex pt1 pt2
+     then pn
+     else pt2
+
+merge_pairs :: Double -> U.Vector (Point,Point) -> U.Vector (Point,Point) -> U.Vector (Point,Point)
+merge_pairs x0 a b
+ = let d  = sqrt (max (U.maximum (U.map dist a)) (U.maximum (U.map dist b)))
+       an = near_boundary a x0 d
+       bn = near_boundary b x0 d
+       a' = a `U.update` new_nearest an bn
+       b' = b `U.update` new_nearest bn an
+   in  a' U.++ b'
+ where
+  dist (a,b) = distancex a b
+
+
+closest :: U.Vector Point -> U.Vector (Point,Point)
+closest pts
+ | U.length pts < 250 = closeststupid pts
+ | otherwise        =
+   let (xs,ys)   = U.unzip pts
+
+       xd   = U.maximum xs - U.minimum xs
+       yd   = U.maximum ys - U.minimum ys
+
+       mid  = median xs
+       
+       top  = U.filter (\(x,_) -> x >= mid) pts
+       bot  = U.filter (\(x,_) -> x <  mid) pts
+
+       top' = closest top
+       bot' = closest bot
+
+   in  merge_pairs mid top' bot'
+
+
+
+
+
+closestV :: U.Vector Point -> U.Vector (Point,Point)
+closestV = closest
+
+closeststupidV :: U.Vector Point -> U.Vector (Point,Point)
+closeststupidV = closeststupid
+
+
+median :: U.Vector Double -> Double
+median xs = median' xs (U.length xs `div` 2)
+
+median':: U.Vector Double -> Int -> Double 
+median' xs k =
+  let p  = xs U.! (U.length xs `div` 2)
+      ls = U.filter (<p) xs
+  in  if   k < (U.length ls)
+      then median' ls k
+      else
+        let gs  = U.filter (>p) xs
+            len = U.length xs - U.length gs
+        in  if   k >= len
+            then median' gs (k - len)
+            else p
+
+
diff --git a/dph-examples/examples/spectral/ClosestPairs/dph/Vector1.hs b/dph-examples/examples/spectral/ClosestPairs/dph/Vector1.hs
new file mode 100644 (file)
index 0000000..8d5729e
--- /dev/null
@@ -0,0 +1,115 @@
+{-# LANGUAGE BangPatterns #-}
+module Vector1 (closest1V, closeststupid1V) where
+import Points2D.Types
+import qualified Data.Vector            as V
+import qualified Data.Vector.Unboxed    as U
+
+-- removed the sqrt here - only some users actually need it
+distance :: Point -> Point -> Double
+distance (x1, y1) (x2, y2)
+  = ( (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) )
+
+-- Distance between two points, but return a very large number if they're the same...
+distancex :: Point -> Point -> Double
+distancex a b
+ = let d = distance a b
+   in  if d == 0 then 1e100 else d
+
+
+-- An n^2 algorithm for finding closest pair.
+-- Our divide and conquer drops back to this once there are few enough points
+closeststupid :: U.Vector Point -> (Point,Point)
+closeststupid pts = merge pts pts
+
+near_boundary :: U.Vector Point -> Double -> Double -> U.Vector Point
+near_boundary pts x0 d
+ = U.filter check pts
+ where
+  check (x1,_) = abs (x1 - x0) < d
+
+
+merge :: U.Vector Point -> U.Vector Point -> (Point,Point)
+merge tops bots
+ = case U.foldl m1 Nothing tops of
+    Nothing    -> error "merge empty vector!"
+    Just (p,_) -> p
+ where
+  m1 s a = U.foldl (m2 a) s bots
+
+  m2 a Nothing b
+   = Just ((a,b),distancex a b)
+  m2 a (Just (pts,d)) b
+   = let d' = distancex a b
+     in  if   d' < d
+         then Just ((a,b),d')
+         else Just (pts,  d)
+
+
+merge_pairs :: Double -> U.Vector Point -> U.Vector Point -> (Point,Point) -> (Point,Point) -> (Point,Point)
+merge_pairs x0 top bot (a1,a2) (b1,b2)
+ = let da   = distancex a1 a2
+       db   = distancex b1 b2
+       min2 = if da < db then (a1,a2) else (b1,b2)
+       mind = min da db
+       d    = sqrt mind
+
+       topn = near_boundary top x0 d
+       botn = near_boundary bot x0 d
+
+   in  if   U.length topn * U.length botn == 0
+       then min2
+       else let 
+               (m,n)= merge topn botn
+               dm   = distancex m n
+            in if dm < mind then (m,n) else min2
+
+
+closest :: U.Vector Point -> (Point,Point)
+closest pts
+ | U.length pts < 250 = closeststupid pts
+ | otherwise       =
+   let (xs,ys)   = U.unzip pts
+
+       xd   = U.maximum xs - U.minimum xs
+       yd   = U.maximum ys - U.minimum ys
+
+       mid  = median xs
+       
+       (top,bot)  = U.partition (\(x,_) -> x >= mid) pts
+
+       top' = closest top
+       bot' = closest bot
+
+   in  merge_pairs mid top bot top' bot'
+
+flip pts
+ = let (xs,ys) = U.unzip pts
+   in  U.zip xs ys
+
+flip2 ((x1,y1),(x2,y2)) = ((y1,x1),(y2,x2))
+
+
+closest1V :: U.Vector Point -> (Point,Point)
+closest1V = closest
+
+closeststupid1V :: U.Vector Point -> (Point,Point)
+closeststupid1V = closeststupid
+
+
+median :: U.Vector Double -> Double
+median xs = median' xs (U.length xs `div` 2)
+
+median':: U.Vector Double -> Int -> Double 
+median' xs k =
+  let p  = xs U.! (U.length xs `div` 2)
+      ls = U.filter (<p) xs
+  in  if   k < (U.length ls)
+      then median' ls k
+      else
+        let gs  = U.filter (>p) xs
+            len = U.length xs - U.length gs
+        in  if   k >= len
+            then median' gs (k - len)
+            else p
+
+
diff --git a/dph-examples/examples/spectral/ClosestPairs/dph/Vectorised.hs b/dph-examples/examples/spectral/ClosestPairs/dph/Vectorised.hs
new file mode 100644 (file)
index 0000000..5a94f01
--- /dev/null
@@ -0,0 +1,120 @@
+{-# LANGUAGE ParallelArrays #-}
+{-# OPTIONS -fvectorise #-}
+{-# OPTIONS -fno-spec-constr-count #-}
+module Vectorised (closestPA, closeststupidPA) where
+import Points2D.Types
+import Data.Array.Parallel
+import Data.Array.Parallel.Prelude.Double        as D
+import qualified Data.Array.Parallel.Prelude.Int as I
+import qualified Prelude as P
+
+distance :: Point -> Point -> Double
+distance (x1, y1) (x2, y2)
+  =   (x2 D.- x1) D.* (x2 D.- x1)
+  D.+ (y2 D.- y1) D.* (y2 D.- y1)
+
+-- Distance between two points, but return a very large number if they're the same...
+distancex :: Point -> Point -> Double
+distancex a b
+ = let d = distance a b
+   in  if d D.== 0 then 1e100 else d
+
+
+bpermuteP as is = mapP (\i -> as !: i) is
+
+-- An n^2 algorithm for finding closest pairs.
+-- Our divide and conquer drops back to this once there are few enough points
+closeststupid :: [: Point :] -> [:(Point,Point):]
+closeststupid pts
+ = let is = [: minIndexP [: distancex a b | b <- pts :] | a <- pts :]
+   in  bpermuteP [: (a,b) | a <- pts, b <- pts :] is
+
+near_boundary :: [:(Point,Point):] -> Double -> Double -> [:(Int,(Point,Point)):]
+near_boundary a x0 d
+ = filterP check (indexedP a)
+ where
+  check (_,((x1,_),_)) = abs (x1 - x0) < d
+
+
+new_nearest :: [:(Int,(Point,Point)):] -> [:(Int,(Point,Point)):] -> [:(Int,(Point,Point)):]
+new_nearest a b
+ | lengthP b I.== 0 = a
+ | otherwise
+ = let bp = mapP (\(_,(pt1,_)) -> pt1) b
+       is = [: minIndexP [: distance pt1 pt2 | pt2 <- bp :] | (_,(pt1,_)) <- a :]
+       na = [: (k,(pt1,check pt1 pn pt2)) | (k,(pt1,pt2)) <- a, pn <- bpermuteP bp is :]
+   in  na
+ where
+  check pt1 pn pt2
+   = if   distance pt1 pn < distance pt1 pt2
+     then pn
+     else pt2
+
+merge_pairs :: Double -> [:(Point,Point):] -> [:(Point,Point):] -> [:(Point,Point):]
+merge_pairs x0 a b
+ = let d  = sqrt (max (maximumP (mapP dist a)) (maximumP (mapP dist b)))
+       an = near_boundary a x0 d
+       bn = near_boundary b x0 d
+       a' = a `updateP` new_nearest an bn
+       b' = b `updateP` new_nearest bn an
+   in  a' +:+ b'
+ where
+  dist (a,b) = distance a b
+
+
+closest :: [:Point:] -> [:(Point,Point):]
+closest pts
+ | lengthP pts I.< 250 = closeststupid pts
+ | otherwise       =
+   let (xs,ys)   = unzipP pts
+
+       xd   = maximumP xs D.- minimumP xs
+       yd   = maximumP ys D.- minimumP ys
+
+       pts' = if yd D.> xd then flip pts else pts
+
+       mid  = median xs
+       
+       top  = filterP (\(x,_) -> x D.>= mid) pts
+       bot  = filterP (\(x,_) -> x D.<  mid) pts
+
+       top' = closest top
+       bot' = closest bot
+
+       pair = merge_pairs mid top' bot'
+   in  if yd D.> xd then flip2 pair else pair
+
+flip pts
+ = let (xs,ys) = unzipP pts
+   in  zipP xs ys
+
+flip2 prs
+ = let (p1,p2) = unzipP prs
+       (x1,y1) = unzipP p1
+       (x2,y2) = unzipP p2
+   in  (zipP y1 x1) `zipP` (zipP y2 x2)
+
+
+closestPA :: PArray Point -> PArray (Point,Point)
+closestPA ps = toPArrayP (closest (fromPArrayP ps))
+
+closeststupidPA :: PArray Point -> PArray (Point,Point)
+closeststupidPA ps = toPArrayP (closeststupid (fromPArrayP ps))
+
+
+median :: [: Double :] -> Double
+median xs = median' xs (lengthP xs `I.div` 2)
+
+median':: [: Double :] -> Int -> Double 
+median' xs k =
+  let p  = xs !: (lengthP xs `I.div` 2)
+      ls = [:x | x <- xs, x D.< p:]
+  in  if   k I.< (lengthP ls)
+      then median' ls k
+      else
+        let gs  = [:x | x <- xs, x D.> p:]
+            len = lengthP xs I.- lengthP gs
+        in  if   k I.>= len
+            then median' gs (k I.- len)
+            else p
+
diff --git a/dph-examples/examples/spectral/ClosestPairs/dph/Vectorised1.hs b/dph-examples/examples/spectral/ClosestPairs/dph/Vectorised1.hs
new file mode 100644 (file)
index 0000000..d8336ee
--- /dev/null
@@ -0,0 +1,114 @@
+{-# LANGUAGE ParallelArrays #-}
+{-# OPTIONS -fvectorise #-}
+{-# OPTIONS -fno-spec-constr-count #-}
+module Vectorised1 (closest1PA, closeststupid1PA) where
+import Points2D.Types
+import Data.Array.Parallel
+import Data.Array.Parallel.Prelude.Double        as D
+import qualified Data.Array.Parallel.Prelude.Int as I
+import qualified Prelude as P
+
+-- removed the sqrt here - only some users actually need it
+distance :: Point -> Point -> Double
+distance (x1, y1) (x2, y2)
+  =      ( (x2 D.- x1) D.* (x2 D.- x1)
+       D.+ (y2 D.- y1) D.* (y2 D.- y1) )
+
+-- Distance between two points, but return a very large number if they're the same...
+distancex :: Point -> Point -> Double
+distancex a b
+ = let d = distance a b
+   in  if d D.== 0 then 1e100 else d
+
+
+-- An n^2 algorithm for finding closest pair.
+-- Our divide and conquer drops back to this once there are few enough points
+closeststupid :: [: Point :] -> (Point,Point)
+closeststupid pts
+ = let i = minIndexP [: distancex a b | a <- pts, b <- pts :]
+   in  [: (a,b) | a <- pts, b <- pts :] !: i
+
+near_boundary :: [:Point:] -> Double -> Double -> [:Point:]
+near_boundary pts x0 d
+ = filterP check pts
+ where
+  check (x1,_) = D.abs (x1 D.- x0) D.< d
+
+
+merge :: [:Point:] -> [:Point:] -> (Point,Point)
+merge tops bots
+ = let i = minIndexP [: distancex a b | a <- tops, b <- bots :]
+   in  [: (a,b) | a <- tops, b <- bots :] !: i
+
+merge_pairs :: Double -> [:Point:] -> [:Point:] -> (Point,Point) -> (Point,Point) -> (Point,Point)
+merge_pairs x0 top bot (a1,a2) (b1,b2)
+ = let da   = distancex a1 a2
+       db   = distancex b1 b2
+       min2 = if da D.< db then (a1,a2) else (b1,b2)
+       mind = D.min da db
+       d    = sqrt mind
+
+       topn = near_boundary top x0 d
+       botn = near_boundary bot x0 d
+
+   in  if   lengthP topn I.* lengthP botn I.== 0
+       then min2
+       else let 
+               (m,n)= merge topn botn
+               dm   = distancex m n
+            in if dm D.< mind then (m,n) else min2
+
+
+closest :: [:Point:] -> (Point,Point)
+closest pts
+ | lengthP pts I.< 250 = closeststupid pts
+ | otherwise       =
+   let (xs,ys)   = unzipP pts
+
+       xd   = maximumP xs D.- minimumP xs
+       yd   = maximumP ys D.- minimumP ys
+
+       pts' = pts -- if yd > xd then flip pts else pts
+
+       mid  = median xs
+       
+       top  = filterP (\(x,_) -> x D.>= mid) pts'
+       -- NOTE was error here "combine2SPack" when "not (x >= mid)"
+       bot  = filterP (\(x,_) -> x D.< mid) pts'
+
+       top' = closest top
+       bot' = closest bot
+
+       pair = merge_pairs mid top bot top' bot'
+   in  pair -- if yd > xd then flip2 pair else pair
+
+flip pts
+ = let (xs,ys) = unzipP pts
+   in  zipP xs ys
+
+flip2 ((x1,y1),(x2,y2)) = ((y1,x1),(y2,x2))
+
+
+closest1PA :: PArray Point -> (Point,Point)
+closest1PA ps = closest (fromPArrayP ps)
+
+closeststupid1PA :: PArray Point -> (Point,Point)
+closeststupid1PA ps = closeststupid (fromPArrayP ps)
+
+
+median :: [: Double :] -> Double
+median xs = median' xs (lengthP xs `I.div` 2)
+
+median':: [: Double :] -> Int -> Double 
+median' xs k =
+  let p  = xs !: (lengthP xs `I.div` 2)
+      ls = [:x | x <- xs, x D.< p:]
+  in  if   k I.< (lengthP ls)
+      then median' ls k
+      else
+        let gs  = [:x | x <- xs, x D.> p:]
+            len = lengthP xs I.- lengthP gs
+        in  if   k I.>= len
+            then median' gs (k I.- len)
+            else p
+