topic Re: oneMKL sorting in Intel® oneAPI Math Kernel Library

oneMKL sorting

geerits — Wed, 22 Dec 2021 12:15:51 GMT

Dear reader,

I'm evaluating the possibility of using MKL instead of IMSL as the latter requests huge fees for commercializing software that contains IMSL routines. Just recently, with some help from the Intel community, I tested the MKL SVD routine, which seems to work just fine. But what about the more basic work like "sorting"? I couldn't find anything. Any comments/suggestions? I also need the indices pertaining to the sorted array.

With kind regards,

Tim.

Re: oneMKL sorting

mecej4 — Wed, 22 Dec 2021 13:30:09 GMT

Sorting is, for a number of reasons, not considered a mathematical topic, and is not to be expected in MKL, which stands for Math Kernel Library. The runtime library of the programming language that you use (C/C++ or Fortran), however, usually provides for sorting.

Please state your requirement more completely -- are you sorting an array of integers, reals, or strings? Or sorting an array of user-defined type? How many items to you expect to sort, and how often? Do you require the order of equal items to be preserved? Is there a specific IMSL sorting routine that you are trying to substitute for?

The IPP library, which is an optional component of OneAPI, contains routines for sorting, as well. However, IPP aims to process arrays of small to medium size, not large size.

Re: oneMKL sorting

geerits — Wed, 22 Dec 2021 15:25:38 GMT

Hi mecej4,

Ok, good to know! Then I assume that searching an array for a value (e.g., <=number) is also not contained in MKL?

I'm using IMSL routine DSVRGP (the double precision version of SVRGP()) to sort an array of type double. I do that on many occasions. The call occurs in a parallelized loop (I use OpenMP, while using the Intel C++ compiler [Version 19]). Although the array sizes (N) differ from call to call, I can say that N<=500. Does that qualify for using the IPP library?

PS: I also need to know the original indices pertaining to the sorted values.

With kind regards,

Tim.

Re: oneMKL sorting

mecej4 — Wed, 22 Dec 2021 19:31:56 GMT

SVRGP/DSVRGP are described in the IMSL documentation to be implementations of Singleton's version of Quicksort. If your need is to do a sort and then search the sorted array with new values, I do not see why you need to form an index array.

If the number of items is around 500, I think that a hybrid sort with quicksort down to partitions of size on the neighborhood of 80, followed by insertion sort of the smaller partitions, is what would be most efficient.

The C library functions qsort() and bsearch() are worth trying. They do not explicitly provide for an index array, but you can achieve the same purpose by using a struct composed of value:index pairs.

Re: oneMKL sorting

ShanmukhS_Intel — Wed, 29 Dec 2021 08:06:33 GMT

Hi,

Has the information provided helped? Kindly let us know if we could close this thread from our end.

Best Regards,

Shanmukh.SS

Re: oneMKL sorting

geerits — Wed, 29 Dec 2021 08:10:39 GMT

Ok, thanks for your info. I'm going to look into this and will let you know about the outcome.

PS: As to your question/statement: "If your need is to do a sort and then search the sorted array with new values, I do not see why you need to form an index array." I just need to know the index in the original array that corresponds to the minimum value of the sorted array (usually the first entry in the sorted array).

Best regards,

Tim.

Re:oneMKL sorting

ShanmukhS_Intel — Mon, 03 Jan 2022 08:43:30 GMT

Hi,

Thanks for accepting the solution. If you need any additional information, please post a new question as this thread will no longer be monitored by Intel.

Best Regards,

Shanmukh.SS