Intel ISA-L EC plugin

Intel ISA-L EC plugin

[Andreas Joachim Peters]

Hi Loic, 

I have chosen after benchmarking to use the LRU cache for the decoding matrix. I can cache easily all decoding matrices (worst case scenario) for configurations up to (10,4) without trashing it. I will restrict the (k,m) in case of the vandermonde matrix to the ones which are invertible, for cauchy they are all invertible anyway.

I will rebase to your branch wip-7238-lrc then!

Cheers Andreas.


________________________________________
From: Loic Dachary [loic@dachary.org]
Sent: 02 July 2014 20:33
To: Andreas Joachim Peters; ceph-devel@vger.kernel.org
Subject: Re: FW: Intel ISA-L EC plugin

Hi Andreas,

On 02/07/2014 19:54, Andreas Joachim Peters wrote:> Hi Sage & Loic et al ...
> getting some support from Paul Luse I have finished the refactoring of the EC ISA-L plug-in.
>
>
> The essential ISA-L v 2.10 sources are now part of the source tree and it builds a single shared library which is portable on platforms with varying CPU extensions (SSE2, AVX, AVX2). I tested on various Intel & AMD processor types.
>
> The build of the plug-in is coupled to the presence of 'yasm' similiar to the crc32c extension in common/ ... (I couldn't build ISA-L on ARM).
>
> It supports two encoding matrices Vandermonde & Cauchy. The techniques are called similar to the one used by Loic in Jerasure "reed_sol_van" & "cauchy". "cauchy" is the default.
>
> Greg Tucker from Intel pointed me to the proper ( and faster ) way of decoding if parity chunks are missing.

Great !

> ??? How do we proceed? I currently rebase against firefly and use its API definition or should this be for a later release with Loic's refactored interface? Shall I make a pull request or shall I hand it over to Loic and he takes care to do the integration including QA etc ...?

It would be great if you could rebase against https://github.com/dachary/ceph/tree/wip-7238-lrc. It contains the base class that will help us share code common to plugins. I hope it will be merged in the next few days. During the last CDS the remapping of the data chunks has been agreed on and the only reason why it is not yet merged is that integration tests must first show it does not break anything and is fully backward compatible.

Cheers

> ??? I have still an open question on the library optimization for decoding(=repair). If you call decoding for a certain set one needs to do a matrix inversion coupled to the given set. If the payload is like 1M the computation of the decoding matrix does not
>  play a role. If the payload is 4k it plays a role. Can I assume that the plugin will be called concurrently for the same object with the same set of chunks or would the plugin be called interleaved for many objects with changing chunk configurations? Is the
>  EC object called single-threaded or by a thread pool? Will backfilll use 4k IOs or larger?
>
> I would either commit the simple cache mechanism caching the last computed erasure configuration & corresponding matrix or put an LRU cache for the last computed matrices. I prototyped both, but would stick to the simplest required.
>
> Cheers Andreas.
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> --
> To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

--
Loïc Dachary, Artisan Logiciel Libre

--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Intel ISA-L EC plugin

[Loic Dachary]

[-- Attachment #1: Type: text/plain, Size: 4009 bytes --]



On 03/07/2014 23:24, Andreas Joachim Peters wrote:> Hi Loic, 
> 
> I have chosen after benchmarking to use the LRU cache for the decoding matrix. I can cache easily all decoding matrices (worst case scenario) for configurations up to (10,4) without trashing it. I will restrict the (k,m) in case of the vandermonde matrix to the ones which are invertible, for cauchy they are all invertible anyway.
> 
> I will rebase to your branch wip-7238-lrc then!

Hi Andreas,

From what I read in https://bitbucket.org/jimplank/jerasure/src/21de98383350e7c46e5ee329de2a93c696dee67a/src/jerasure.c?at=master#cl-167 it looks like it could benefit from a LRU cache also. Are you going to use https://github.com/ceph/ceph/blob/master/src/include/lru.h for this ?

Cheers
> 
> Cheers Andreas.
> 
> 
> ________________________________________
> From: Loic Dachary [loic@dachary.org]
> Sent: 02 July 2014 20:33
> To: Andreas Joachim Peters; ceph-devel@vger.kernel.org
> Subject: Re: FW: Intel ISA-L EC plugin
> 
> Hi Andreas,
> 
> On 02/07/2014 19:54, Andreas Joachim Peters wrote:> Hi Sage & Loic et al ...
>> getting some support from Paul Luse I have finished the refactoring of the EC ISA-L plug-in.
>>
>>
>> The essential ISA-L v 2.10 sources are now part of the source tree and it builds a single shared library which is portable on platforms with varying CPU extensions (SSE2, AVX, AVX2). I tested on various Intel & AMD processor types.
>>
>> The build of the plug-in is coupled to the presence of 'yasm' similiar to the crc32c extension in common/ ... (I couldn't build ISA-L on ARM).
>>
>> It supports two encoding matrices Vandermonde & Cauchy. The techniques are called similar to the one used by Loic in Jerasure "reed_sol_van" & "cauchy". "cauchy" is the default.
>>
>> Greg Tucker from Intel pointed me to the proper ( and faster ) way of decoding if parity chunks are missing.
> 
> Great !
> 
>> ??? How do we proceed? I currently rebase against firefly and use its API definition or should this be for a later release with Loic's refactored interface? Shall I make a pull request or shall I hand it over to Loic and he takes care to do the integration including QA etc ...?
> 
> It would be great if you could rebase against https://github.com/dachary/ceph/tree/wip-7238-lrc. It contains the base class that will help us share code common to plugins. I hope it will be merged in the next few days. During the last CDS the remapping of the data chunks has been agreed on and the only reason why it is not yet merged is that integration tests must first show it does not break anything and is fully backward compatible.
> 
> Cheers
> 
>> ??? I have still an open question on the library optimization for decoding(=repair). If you call decoding for a certain set one needs to do a matrix inversion coupled to the given set. If the payload is like 1M the computation of the decoding matrix does not
>>  play a role. If the payload is 4k it plays a role. Can I assume that the plugin will be called concurrently for the same object with the same set of chunks or would the plugin be called interleaved for many objects with changing chunk configurations? Is the
>>  EC object called single-threaded or by a thread pool? Will backfilll use 4k IOs or larger?
>>
>> I would either commit the simple cache mechanism caching the last computed erasure configuration & corresponding matrix or put an LRU cache for the last computed matrices. I prototyped both, but would stick to the simplest required.
>>
>> Cheers Andreas.
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
> 
> --
> Loïc Dachary, Artisan Logiciel Libre
> 

-- 
Loïc Dachary, Artisan Logiciel Libre


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 263 bytes --]

Re: Intel ISA-L EC plugin

[Xavier Hernandez]

On Thursday 03 July 2014 21:24:59 Andreas Joachim Peters wrote:
> Hi Loic,
> 
> I have chosen after benchmarking to use the LRU cache for the decoding
> matrix. I can cache easily all decoding matrices (worst case scenario) for
> configurations up to (10,4) without trashing it. I will restrict the (k,m)
> in case of the vandermonde matrix to the ones which are invertible, for
> cauchy they are all invertible anyway.

Maybe I'm misunderstanding something because I haven't had time to analyze ec 
code.

AFAIK the only condition that a Vandermonde matrix needs to be invertible is 
to have all rows different (i.e. use a different base number for each row). Do 
you have matrices with duplicated rows ? or there is some property I don't 
know ?

Thanks,

Xavi

RE: Intel ISA-L EC plugin

[Andreas Joachim Peters]

Hi Xavi, 
I had the same understanding. However the decoding routine is not always able to invert the given matrix. This can be either due to the generator matrix which does not conserve the MDS property, the matrix inversion procedure or a bug on my side I will check carefully my code and the input I provide. I already asked the maintainer of the library who put me on that path and there are also inline comments about non invertible vandermonde matrices in the code. However if I switch to a cauchy matrix I never see any problem with the code.

Cheers Andreas.

________________________________________
From: Xavier Hernandez [xhernandez@datalab.es]
Sent: 04 July 2014 09:43
To: Andreas Joachim Peters
Cc: Loic Dachary; ceph-devel@vger.kernel.org
Subject: Re: Intel ISA-L EC plugin

On Thursday 03 July 2014 21:24:59 Andreas Joachim Peters wrote:
> Hi Loic,
>
> I have chosen after benchmarking to use the LRU cache for the decoding
> matrix. I can cache easily all decoding matrices (worst case scenario) for
> configurations up to (10,4) without trashing it. I will restrict the (k,m)
> in case of the vandermonde matrix to the ones which are invertible, for
> cauchy they are all invertible anyway.

Maybe I'm misunderstanding something because I haven't had time to analyze ec
code.

AFAIK the only condition that a Vandermonde matrix needs to be invertible is
to have all rows different (i.e. use a different base number for each row). Do
you have matrices with duplicated rows ? or there is some property I don't
know ?

Thanks,

Xavi

RE: Intel ISA-L EC plugin

[Andreas Joachim Peters]

Hi Loic, 
probably one should do the same trick for Jerasure. However in the most common situation (one lost), the decoding matrix is not generated anyway.

I used std::map + std::list where the map value is a pair with the iterator pointing into the list + the matrix and I use the splice function to move an LRU entry in the list. The key is just a string defining the decoding situation (erasures). I can also use lru.h ... should give the same performance.

Cheers Andreas.

>
> I have chosen after benchmarking to use the LRU cache for the decoding matrix. I can cache easily all decoding matrices (worst case scenario) for configurations up to (10,4) without trashing it. I will restrict the (k,m) in case of the vandermonde matrix to the ones which are invertible, for cauchy they are all invertible anyway.
>
> I will rebase to your branch wip-7238-lrc then!

Hi Andreas,

From what I read in https://bitbucket.org/jimplank/jerasure/src/21de98383350e7c46e5ee329de2a93c696dee67a/src/jerasure.c?at=master#cl-167 it looks like it could benefit from a LRU cache also. Are you going to use https://github.com/ceph/ceph/blob/master/src/include/lru.h for this ?

Cheers
>
> Cheers Andreas.
>
>
> ________________________________________
> From: Loic Dachary [loic@dachary.org]
> Sent: 02 July 2014 20:33
> To: Andreas Joachim Peters; ceph-devel@vger.kernel.org
> Subject: Re: FW: Intel ISA-L EC plugin
>
> Hi Andreas,
>
> On 02/07/2014 19:54, Andreas Joachim Peters wrote:> Hi Sage & Loic et al ...
>> getting some support from Paul Luse I have finished the refactoring of the EC ISA-L plug-in.
>>
>>
>> The essential ISA-L v 2.10 sources are now part of the source tree and it builds a single shared library which is portable on platforms with varying CPU extensions (SSE2, AVX, AVX2). I tested on various Intel & AMD processor types.
>>
>> The build of the plug-in is coupled to the presence of 'yasm' similiar to the crc32c extension in common/ ... (I couldn't build ISA-L on ARM).
>>
>> It supports two encoding matrices Vandermonde & Cauchy. The techniques are called similar to the one used by Loic in Jerasure "reed_sol_van" & "cauchy". "cauchy" is the default.
>>
>> Greg Tucker from Intel pointed me to the proper ( and faster ) way of decoding if parity chunks are missing.
>
> Great !
>
>> ??? How do we proceed? I currently rebase against firefly and use its API definition or should this be for a later release with Loic's refactored interface? Shall I make a pull request or shall I hand it over to Loic and he takes care to do the integration including QA etc ...?
>
> It would be great if you could rebase against https://github.com/dachary/ceph/tree/wip-7238-lrc. It contains the base class that will help us share code common to plugins. I hope it will be merged in the next few days. During the last CDS the remapping of the data chunks has been agreed on and the only reason why it is not yet merged is that integration tests must first show it does not break anything and is fully backward compatible.
>
> Cheers
>
>> ??? I have still an open question on the library optimization for decoding(=repair). If you call decoding for a certain set one needs to do a matrix inversion coupled to the given set. If the payload is like 1M the computation of the decoding matrix does not
>>  play a role. If the payload is 4k it plays a role. Can I assume that the plugin will be called concurrently for the same object with the same set of chunks or would the plugin be called interleaved for many objects with changing chunk configurations? Is the
>>  EC object called single-threaded or by a thread pool? Will backfilll use 4k IOs or larger?
>>
>> I would either commit the simple cache mechanism caching the last computed erasure configuration & corresponding matrix or put an LRU cache for the last computed matrices. I prototyped both, but would stick to the simplest required.
>>
>> Cheers Andreas.
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
>
> --
> Loïc Dachary, Artisan Logiciel Libre
>

--
Loïc Dachary, Artisan Logiciel Libre

--
To unsubscribe from this list: send the line "unsubscribe ceph-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html