Opened 3 years ago
Closed 18 months ago
#7091 closed bug (invalid)
DPH Matrix product memory usage
Reported by: | mblanco | Owned by: | benl |
---|---|---|---|
Priority: | normal | Milestone: | 7.8.1 |
Component: | Data Parallel Haskell | Version: | 7.4.1 |
Keywords: | Cc: | ||
Operating System: | Linux | Architecture: | x86 |
Type of failure: | Runtime performance bug | Test Case: | |
Blocked By: | Blocking: | ||
Related Tickets: | Differential Revisions: |
Description (last modified by igloo)
This report is from the post at Haskell-cafe "DPH matrix product", I'm reporting it here so developers can define if it's a bug or not and its priority.
On a (I think) standar implementation of matrix product on DPH I notice an excessive use of system memory.
At execution time, on matrices of size 300*300 the program does finish (although it is very slow), but on 600*600 it consumes GBs of RAM until the process is aborted.
This is the system information:
- Ubuntu 12.04 32-bit
- Intel® Core™2 Duo CPU T5270 @ 1.40GHz × 2
- 2.9 GiB RAM
GHC version:
- GHC 7.4.1
DPH libraries:
- dph-base-0.6.1.1
- (dph-lifted-base-0.6.1.1)
- (dph-lifted-vseg-0.6.1.2)
- (dph-prim-interface-0.6.1.1)
- (dph-prim-par-0.6.1.1)
- (dph-prim-seq-0.6.1.1)
Compilation flags:
I'm using two combinations of flags, taken from different sources. In both cases results are identical:
- From https://github.com/ghc/packages-dph: -rtsopts -threaded -fllvm -optlo-O3 -Odph -fcpr-off -fno-liberate-case -package dph-lifted-vseg
- From dph-examples: -rtsopts -threaded -fllvm -Odph -package dph-lifted-vseg -fcpr-off -fno-liberate-case -fsimpl-tick-factor=1000
Execution flags:
+RTS -N
Tests:
- Computing the product of two 400*400 matrices takes 6.037993 seconds.
- Computing the product of two 600*600 matrices yields "out of memory (requested 1728053248 bytes)".
DPH code:
{-# LANGUAGE ParallelArrays, ParallelListComp #-} {-# OPTIONS -fvectorise #-} module DPH_mmult_wrapper (matMult_wrapper, Matrix_wrapper) where import qualified Prelude import Data.Array.Parallel import Data.Array.Parallel.Prelude.Double as D import Data.Array.Parallel.Prelude.Int as I type MMultType = Double type Matrix = [:[:MMultType:]:] type MVector = [:MMultType:] type Matrix_wrapper = PArray (PArray MMultType) -- matMult_wrapper assumes mB is already transposed {-# NOINLINE matMult_wrapper #-} matMult_wrapper :: Matrix_wrapper -> Matrix_wrapper -> Matrix_wrapper matMult_wrapper mA mB = toPArrayP (mapP toPArrayP (matMult (fromNestedPArrayP mA) (fromNestedPArrayP mB))) matMult :: Matrix -> Matrix -> Matrix matMult mA mB = mapP (\row -> mapP (\col -> dotp row col) mB) mA dotp :: MVector -> MVector -> MMultType dotp row col = D.sumP (zipWithP (D.*) row col)
I'm reporting this as I think it is the kind of problems intended to be solved in the last definition of the internal DPH structure (the one from "Work Efficient Higher-Order Vectorisation" paper).
If there is any information missing, please comment and I will update the report.
Thanks.
Change History (6)
comment:1 Changed 3 years ago by igloo
- Description modified (diff)
- difficulty set to Unknown
comment:2 Changed 3 years ago by igloo
- Milestone set to 7.8.1
- Owner set to benl
comment:3 Changed 3 years ago by benl
- Blocked By 7330 added
comment:4 Changed 3 years ago by benl
- Blocked By 7330 removed
The paper claims *work* efficient vectorisation, not *space* efficient vectorisation. Making it space efficient is an open research question.
comment:5 Changed 18 months ago by George
More specifially, in section 5.5 the paper states:
nested parallelism can increase the asymptotic space complexity
in a way that this paper does not address [15, 19]. ...
The flattened version is a hylomorphism that first computes O(n^2)
distances before reducing them to determine the maximum. Whereas
the sequential version would run in O(n) space, the flattened version
needs O(n^2) space to hold the intermediate vector of distances.
Given the preceding this issue seems to be a known consequence of the dph algorithm and as such the status of this should be "Not a bug" as it is not a GHC bug. However this is just my opinion and I don't feel I have the expertise to actually change the bug status
comment:6 Changed 18 months ago by benl
- Resolution set to invalid
- Status changed from new to closed
I've set it to invalid to clean up the ticket data base.
This is a research problem, not a bug in the compiler.
Ben, could you take a look please?