Opened 3 years ago

Closed 20 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 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

Ben, could you take a look please?

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 20 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 20 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.

Note: See TracTickets for help on using tickets.