Groups > linux.debian.user > #160237 > unrolled thread

How to write optimized code for an instruction set not supported by my computer?

Started by	Mario Castelán Castro <marioxcc.MT@yandex.com>
First post	2015-11-05 23:40 +0100
Last post	2015-11-14 02:20 +0100
Articles	16 — 5 participants

Back to article view | Back to linux.debian.user

#160237 — How to write optimized code for an instruction set not supported by my computer?

From	Mario Castelán Castro <marioxcc.MT@yandex.com>
Date	2015-11-05 23:40 +0100
Subject	How to write optimized code for an instruction set not supported by my computer?
Message-ID	<qrBmh-4ms-3@gated-at.bofh.it>

Hello.

What is the usual workflow to write code that takes advantage of an 
instruction set that is not present in my computer (either in assembly 
or using intrinsic functions that represent those instructions in an 
higher level language)?. For example, if I want to write code for 
decoding and encoding Base64 that uses AVX instructions in my machine 
that has no support for any version of AVX (only SSE 4.2 and CLMUL), 
what is the recommended workflow?.

It seems like I *could* develop within a virtual machine emulated with 
Bochs that supports these instructions, but that would give a very big 
overhead, since I would have to emulate a whole system, and Bochs has no 
multithreading support (so that will make it less efficient if I want to 
write multithreaded code). Is there a better option?

Regards and thanks in advance.

[toc] | [next] | [standalone]

#160239

From	Mario Castelán Castro <marioxcc.MT@yandex.com>
Date	2015-11-06 00:40 +0100
Message-ID	<qrCim-57c-11@gated-at.bofh.it>
In reply to	#160237

I forgot to mention that I am only looking for free as in freedom tools. 
I refuse to use proprietary tools, including proprietary CPU emulators.

[toc] | [prev] | [next] | [standalone]

#160243

From	<tomas@tuxteam.de>
Date	2015-11-06 15:50 +0100
Message-ID	<qrQv0-5Lv-31@gated-at.bofh.it>
In reply to	#160239

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thu, Nov 05, 2015 at 05:34:07PM -0600, Mario Castelán Castro wrote:
> I forgot to mention that I am only looking for free as in freedom
> tools. I refuse to use proprietary tools, including proprietary CPU
> emulators.

This link might be relevant:

  <http://superuser.com/questions/453786/how-do-i-get-avx-support-in-qemu>

Besides Intel's Software Development Emulator, which seems to have pretty
burdensome license terms (on a superficial read -- it seems you have to
download the whole gorilla to just read the license, duh) it seems that
Bochs is the way to go?

regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEYEARECAAYFAlY8s9QACgkQBcgs9XrR2kbe5ACfUSt9iMyfqEAFV2RViekWSbeC
bfkAn2eHHWFMqFGsjMfPqsAZWbwmv2Yr
=t60o
-----END PGP SIGNATURE-----

[toc] | [prev] | [next] | [standalone]

#160247

From	Joel Rees <joel.rees@gmail.com>
Date	2015-11-06 19:40 +0100
Message-ID	<qrU5z-875-7@gated-at.bofh.it>
In reply to	#160243

On Fri, Nov 6, 2015 at 11:06 PM,  <tomas@tuxteam.de> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Thu, Nov 05, 2015 at 05:34:07PM -0600, Mario Castelán Castro wrote:
>> I forgot to mention that I am only looking for free as in freedom
>> tools. I refuse to use proprietary tools, including proprietary CPU
>> emulators.
>
> This link might be relevant:
>
>   <http://superuser.com/questions/453786/how-do-i-get-avx-support-in-qemu>
>
> Besides Intel's Software Development Emulator, which seems to have pretty
> burdensome license terms (on a superficial read -- it seems you have to
> download the whole gorilla to just read the license, duh)

(I'd be complaining about people still drinking the Intel koolaid, but
what can we do about that? AVX is already their koolaid.

Oh, nevermind.)

> it seems that
> Bochs is the way to go?
>
> regards
> - -- tomás
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.12 (GNU/Linux)
>
> iEYEARECAAYFAlY8s9QACgkQBcgs9XrR2kbe5ACfUSt9iMyfqEAFV2RViekWSbeC
> bfkAn2eHHWFMqFGsjMfPqsAZWbwmv2Yr
> =t60o
> -----END PGP SIGNATURE-----
>



-- 
Joel Rees

Be careful when you look at conspiracy.
Arm yourself with knowledge of yourself, as well:
http://reiisi.blogspot.jp/2011/10/conspiracy-theories.html

[toc] | [prev] | [next] | [standalone]

#160242

From	Darac Marjal <mailinglist@darac.org.uk>
Date	2015-11-06 15:20 +0100
Message-ID	<qrQ1Y-5z3-5@gated-at.bofh.it>
In reply to	#160237

[Multipart message — attachments visible in raw view] — view raw

On Thu, Nov 05, 2015 at 04:33:02PM -0600, Mario Castelán Castro wrote:

>Hello.
>
>What is the usual workflow to write code that takes advantage of an 
>instruction set that is not present in my computer (either in assembly 
>or using intrinsic functions that represent those instructions in an 
>higher level language)?. For example, if I want to write code for 
>decoding and encoding Base64 that uses AVX instructions in my machine 
>that has no support for any version of AVX (only SSE 4.2 and CLMUL), 
>what is the recommended workflow?.

Is the intention to eventually run this code on a system that does 
support that instruction? If so, then yes, emulation should do the job.  
As you mention, it will be slower than native, but it will execute 
enough for debugging.

If you only ever intend to run it on a machine that doesn't support that 
instruction then... what's the point?

>
>It seems like I *could* develop within a virtual machine emulated with 
>Bochs that supports these instructions, but that would give a very big 
>overhead, since I would have to emulate a whole system, and Bochs has 
>no multithreading support (so that will make it less efficient if I 
>want to write multithreaded code). Is there a better option?

I doubt that, even if the Bochs emulator is single-threaded, it doesn't 
support multiple threads in the emulated system. The nature of threads 
is that they're handled by the kernel, rather than the CPU.

Another alternative would be QEMU, which allows you to assign multiple 
vCPUs to a system.

>
>Regards and thanks in advance.
>

-- For more information, please reread.

[toc] | [prev] | [next] | [standalone]

#160248

From	Joel Rees <joel.rees@gmail.com>
Date	2015-11-06 20:10 +0100
Message-ID	<qrUyC-60-9@gated-at.bofh.it>
In reply to	#160237

On Fri, Nov 6, 2015 at 7:33 AM, Mario Castelán Castro
<marioxcc.MT@yandex.com> wrote:
> Hello.
>
> What is the usual workflow to write code that takes advantage of an
> instruction set that is not present in my computer

You're asking one question here.

> (either in assembly or
> using intrinsic functions that represent those instructions in an higher
> level language)?.

You're asking a different question here.

> For example, if I want to write code for decoding and
> encoding Base64 that uses AVX instructions

You're beggin a question here, and I will ask it --

Why on earth would you want to go to the bother of using AVX
instructions for working with Base64?

And the answer to that question is that you have something else you
want to do and you are using Base64 as a MacGuffin. Which is not a
problem for me, but might be a problem for you.

The question being begged is this -- Do you really want to use AVX
enough to sign the Intel agreement that you can't read unless you
agree to it before you read it so you can download it and read it?

It *is* a valid question, and I can't tell you the answer to that.
Maybe you can't answer that question yourself yet.

> in my machine that has no support
> for any version of AVX (only SSE 4.2 and CLMUL), what is the recommended
> workflow?.

The real workflow is that, if you have real reason (not Base64, of
course), you get the hardware now. And you trust Intel not to ask for
your first-born son (speaking figuratively) and sign the agreement and
use their emulator.

Both.

Running the emulator on hardware that can actually run the
instructions is a very useful debugging tool to help you debug your
understanding of the instruction set. (Writing your own emulator can
help, as well, but it may not be worth the time investment.)

> It seems like I *could* develop within a virtual machine emulated with Bochs
> that supports these instructions, but that would give a very big overhead,
> since I would have to emulate a whole system, and Bochs has no
> multithreading support (so that will make it less efficient if I want to
> write multithreaded code).

There are several ways to support multithreading in emulation. Well,
we can say two main ways --

Write it yourself (in other words, as co-operative multi-tasking in
the emulator core code, and some support routines to make it appear
pre-emptive multi-processing to the running application).

Or, let the OS handle it (in other words, someone else has already
written the co-operative part and hopefully mapped it to actual OS
calls that can give both the appearance and advantages of
multi-processing).

> Is there a better option?

>From what the others have said about AVX, if you need to use for
something real (not Base64, of course), you're going ot have to roll
up your sleeves and do some of the grunt work yourself.

If you really do mean Base64 (in other words, if you just want to play
or this is a homework project or something), well, you have to decide
whether you want to trust Intel and sign their agreement and download
their emulator just to play or do a homework assignment or something.

And maybe, once you have real specs in your hands, write your own
emulator to help you cut through the sales talk in the specs. (Bochs
or QEMU might help you at this step.)

And expect that what you learn will only be partly applicable in the real world.

> Regards and thanks in advance.
>

Hope that helps.

-- 
Joel Rees

Be careful when you look at conspiracy.
Arm yourself with knowledge of yourself, as well:
http://reiisi.blogspot.jp/2011/10/conspiracy-theories.html

[toc] | [prev] | [next] | [standalone]

#160330

From	Mario Castelán Castro <marioxcc.MT@yandex.com>
Date	2015-11-09 00:00 +0100
Message-ID	<qsH6i-6m1-5@gated-at.bofh.it>
In reply to	#160237

<tomas@tuxteam.de> writes:
> This link might be relevant:
>
>   <http://superuser.com/questions/453786/how-do-i-get-avx-support-in-qemu>
>
> Besides Intel's Software Development Emulator, which seems to have pretty
> burdensome license terms (on a superficial read -- it seems you have to
> download the whole gorilla to just read the license, duh) it seems that
> Bochs is the way to go?

I have encountered that superuser.com question previously. It does not 
really provide a solution. It mentions an experimental extension to QEMU 
(an old version of QEMU) that implements some AVX instructions. I am 
wary of software like that. It seems to be done more as a proof of 
concept and as an exercise than a something intended for "production" usage.

mailinglist@darac.org.uk writes:
> Is the intention to eventually run this code on a system that does support that instruction? If so, then yes, emulation should do the job.  As you mention, it will be slower than native, but it will execute enough for debugging.
>
> If you only ever intend to run it on a machine that doesn't support that instruction then... what's the point?

Yes, the code will be eventually run on a system with native support for 
the instructions.

mailinglist@darac.org.uk writes:
> I doubt that, even if the Bochs emulator is single-threaded, it doesn't support multiple threads in the emulated system. The nature of threads is that they're handled by the kernel, rather than the CPU.
>
> Another alternative would be QEMU, which allows you to assign multiple vCPUs to a system.

QEMU does not support AVX as far as I know.

The problem with Bochs and multithreading that I was referring to is 
that although the OS can handle multiple threads just as well on a 
single core system than on a multiple core system, the threads won't run 
on parallel; that has effects on performance which are not present on a 
real multithreaded systems, and those effects should be accounted for 
when tunning for performance.

joel.rees@gmail.com writes:
> Why on earth would you want to go to the bother of using AVX
> instructions for working with Base64?

For performance, of course. That is always the case when explicitly 
using some instructions in specific (rather than leaving it to the 
compiler to decide which instructions to use).

joel.rees@gmail.com writes:
> The question being begged is this -- Do you really want to use AVX
> enough to sign the Intel agreement that you can't read unless you
> agree to it before you read it so you can download it and read it?
>
> It *is* a valid question, and I can't tell you the answer to that.
> Maybe you can't answer that question yourself yet.

No, I am not willing to use Intel's proprietary tools. In an earlier 
message in the same thread I said that I avoid proprietary software. 
That is one of the reasons of why I use Debian: It is easy to avoid the 
proprietary software.

-----

Thanks to everybody who replied. I will probably use Bochs when time 
comes to port the algorithm to AVX. Right now I am writing and 
perfecting it in portable C, to have a base result against which to 
compare performance and complexity.

Regards.

[toc] | [prev] | [next] | [standalone]

#160339

From	<tomas@tuxteam.de>
Date	2015-11-09 10:20 +0100
Message-ID	<qsQMi-4tx-9@gated-at.bofh.it>
In reply to	#160330

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Sun, Nov 08, 2015 at 04:54:45PM -0600, Mario Castelán Castro wrote:
> <tomas@tuxteam.de> writes:
> >This link might be relevant:
> >
> >  <http://superuser.com/questions/453786/how-do-i-get-avx-support-in-qemu>
> >
> >Besides Intel's Software Development Emulator, which seems to have pretty
> >burdensome license terms (on a superficial read -- it seems you have to
> >download the whole gorilla to just read the license, duh) it seems that
> >Bochs is the way to go?
> 
> I have encountered that superuser.com question previously. It does
> not really provide a solution. It mentions an experimental extension
> to QEMU (an old version of QEMU) that implements some AVX
> instructions. I am wary of software like that. It seems to be done
> more as a proof of concept and as an exercise than a something
> intended for "production" usage.

This was my take-away from there too: *if* anything is worth trying,
then Bochs (unless mumble mumble Intel -- but their license texts
would scare *me* away. And then people complain about GPL... but
I disgress).

> QEMU does not support AVX as far as I know.
> 
> The problem with Bochs and multithreading that I was referring to is
> that although the OS can handle multiple threads just as well on a
> single core system than on a multiple core system, the threads won't
> run on parallel; that has effects on performance which are not
> present on a real multithreaded systems, and those effects should be
> accounted for when tunning for performance.

I see. But a soft emulation won't give you an idea of performance
anyway? Just thinking about the whole mess from caching down to
instruction set (all of which the emulator has wildly different
timings for)... I'd guess that the single/multi-thread issue is
just a ripple in a sea of uncertainty.

I think expecting just a guess for the timings from an emulator
(at least at this level) is too much. You'd be better off with
your back-of-theenvelope calculations (and then testing, once you
get your hands on "real" hardware).

[...]

> No, I am not willing to use Intel's proprietary tools. In an earlier
> message in the same thread I said that I avoid proprietary software.
> That is one of the reasons of why I use Debian: It is easy to avoid
> the proprietary software.

Phew ;-)

regards
- -- tomás
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEYEARECAAYFAlZAWzQACgkQBcgs9XrR2kZxxACeLd9MjnsbjtzVj+8N+wJlwIaW
v+8AoIH/eX9yY1j1IIck41FIJajZTxUI
=Jc6I
-----END PGP SIGNATURE-----

[toc] | [prev] | [next] | [standalone]

#160349 — Re: How to write optimized code for an instruction set not supported by my computer?

From	Stefan Monnier <monnier@iro.umontreal.ca>
Date	2015-11-09 15:10 +0100
Subject	Re: How to write optimized code for an instruction set not supported by my computer?
Message-ID	<qsViV-7qm-9@gated-at.bofh.it>
In reply to	#160330

>> Why on earth would you want to go to the bother of using AVX
>> instructions for working with Base64?
> For performance, of course.

I think the question was: what makes you think AVX will improve
the performance of *your* code?  Base64 encoding/decoding should be
completely bandwidth-constrained, so it seems very unlikely that AVX
could make much of a difference.


        Stefan

[toc] | [prev] | [next] | [standalone]

#160537

From	Mario Castelán Castro <marioxcc.MT@yandex.com>
Date	2015-11-14 01:10 +0100
Message-ID	<quwzM-4US-17@gated-at.bofh.it>
In reply to	#160330

tomas@tuxteam.de writes:
> I see. But a soft emulation won't give you an idea of performance
> anyway? Just thinking about the whole mess from caching down to
> instruction set (all of which the emulator has wildly different
> timings for)... I'd guess that the single/multi-thread issue is
> just a ripple in a sea of uncertainty.
>
> I think expecting just a guess for the timings from an emulator
> (at least at this level) is too much. You'd be better off with
> your back-of-theenvelope calculations (and then testing, once you
> get your hands on "real" hardware).

I agree. Thanks for pointing this reasoning.

monnier@iro.umontreal.ca writes:
> I think the question was: what makes you think AVX will improve
> the performance of *your* code?  Base64 encoding/decoding should be
> completely bandwidth-constrained, so it seems very unlikely that AVX
> could make much of a difference.

Maybe it's bandwidth constrained; I can't tell beforehand (and I don't 
think you can either); I could only said that with some certainty after 
doing tests.

I did some limited testing but not enough yet. Depending on the testing 
method and the specific Base64 implementation, memcpy is significantly 
faster than a typical lookup table in memory implementation of Base64; 
indicating that computation has a non-negligible role in performance 
(opposed to being memory constrained).

Answering your question: What makes me think that AVX, SSE, or similar 
SIMD instruction sets will improve the performance of my code is:

[1] SIMD instructions are more efficient for copying memory because they 
have less dispatch overhead since they copy in bigger blocks. memcpy 
usually takes advantage of that; so there is a benefit in the case that 
the problem is bandwidth constrained.

[2] Although Base64 is usually implemented with a lookup table, the 
encoding can be performed by relatively simple arithmetical 
computations, because the mapping can be described by bit expansion (6 
bits to 8) and mapping a few continuous input ranges to output ranges. 
For example: 0 to 25 are mapped to 'A' (ASCII 65) to 'B' (ASCII 90).

[3]: A lookup table implementation access the input data *and* the 
lookup table; replacing the lookup table with SIMD arithmetic reduces 
the demand on memory (including cache) throughput.

I do not claim to be certain that this will improve performance, but 
there is a very good possibility that it does, and I will know (in my 
particular case, for my particular CPU) after completing my implementation.

Regards.

[toc] | [prev] | [next] | [standalone]

#160547

From	Joel Rees <joel.rees@gmail.com>
Date	2015-11-14 02:40 +0100
Message-ID	<quxYR-5Jf-1@gated-at.bofh.it>
In reply to	#160537

On Sat, Nov 14, 2015 at 9:08 AM, Mario Castelán Castro
<marioxcc.MT@yandex.com> wrote:
> [...]
> monnier@iro.umontreal.ca writes:
>>
>> I think the question was: what makes you think AVX will improve
>> the performance of *your* code?  Base64 encoding/decoding should be
>> completely bandwidth-constrained, so it seems very unlikely that AVX
>> could make much of a difference.
>
> Maybe it's bandwidth constrained; I can't tell beforehand (and I don't think
> you can either);

Some of us do have experience working with base64.  :)

> I could only said that with some certainty after doing
> tests.
>
> I did some limited testing but not enough yet. Depending on the testing
> method and the specific Base64 implementation, memcpy is significantly
> faster than a typical lookup table in memory implementation of Base64;

memcpy() is a special case. There is usually no computation in the
inner loop(s), although there will often be some carefully crafted
setup and/or loop unrolling, often hand-written to avoid vagueries of
compiler optimimization (and resulting bad interaction with cache
controllers, etc.). (On some CPUs, there is no inner loop, memcpy
being handed off to DMA, but that also implies some scheduling policy
relative to the DMA controller hardware.)

Do you use the -S option to get assembly language output to look at?

> indicating that computation has a non-negligible role in performance
> (opposed to being memory constrained).
>
> Answering your question: What makes me think that AVX, SSE, or similar SIMD
> instruction sets will improve the performance of my code is:
>
> [1] SIMD instructions are more efficient for copying memory because they
> have less dispatch overhead since they copy in bigger blocks. memcpy usually
> takes advantage of that; so there is a benefit in the case that the problem
> is bandwidth constrained.

Yeah, SIMD instructions can also be used as a rather expensive
substitute for pure DMA. Expensive because they are used for more than
pure data move.

> [2] Although Base64 is usually implemented with a lookup table, the encoding
> can be performed by relatively simple arithmetical computations, because the
> mapping can be described by bit expansion (6 bits to 8) and mapping a few
> continuous input ranges to output ranges. For example: 0 to 25 are mapped to
> 'A' (ASCII 65) to 'B' (ASCII 90).

Those computations aren't as simple as you might think. Quite a bit of
branching, and the instruction cache having to restart, etc. It's
defnitely not SIMD, unless your SIMD has table lookup that can operate
independently in each data stream.

> [3]: A lookup table implementation access the input data *and* the lookup
> table;

That's a really small table. Thirty years ago, it would have caused
cache thrashing. Not so much now.

> replacing the lookup table with SIMD arithmetic reduces the demand on
> memory (including cache) throughput.

Does the AVX have that kind of table access? If you have a url for the
relevant specs, I'd be interested.

> I do not claim to be certain that this will improve performance, but there
> is a very good possibility that it does, and I will know (in my particular
> case, for my particular CPU) after completing my implementation.
>
> Regards.
>

-- 
Joel Rees

Be careful when you look at conspiracy.
Arm yourself with knowledge of yourself, as well:
http://reiisi.blogspot.jp/2011/10/conspiracy-theories.html

[toc] | [prev] | [next] | [standalone]

#160565

From	Mario Castelán Castro <marioxcc.MT@yandex.com>
Date	2015-11-14 16:30 +0100
Message-ID	<quKW5-5Jb-1@gated-at.bofh.it>
In reply to	#160547

El 13/11/15 a las 19:32, Joel Rees escribió:
> Do you use the -S option to get assembly language output to look at?

Yes.

> Yeah, SIMD instructions can also be used as a rather expensive
> substitute for pure DMA. Expensive because they are used for more than
> pure data move.

What do you mean by "pure DMA" in this context?. If you mean "direct 
memory access", that is a concept that applies to peripherals who access 
memory directly, not the CPU.

> Those computations aren't as simple as you might think. Quite a bit of
> branching, and the instruction cache having to restart, etc. It's
> defnitely not SIMD, unless your SIMD has table lookup that can operate
> independently in each data stream.

The computation does not require any branching (looping throughout the 
array not counted as part of the computation). Conditional expressions 
are evaluated using masks. I have already implemented it that way 
processing 48 input bits at a time that expand to 64 output bits, using 
64 bits integers. It's like SSE or AVX, but the distinction between 
vector elements is done completely in software; as far as hardware is 
concerned it's 64 bits logic and arithmetic. This implementation is like 
a "prototype" that I made so that I could actually evaluate how complex 
it is. It is simpler than I thought; with SSE or AVX it will be simpler 
still, since they have the separation between vector elements built in 
and have instructions dedicated to making masks and shuffling data.

Also, SSE can process 96 bits of input that expand to 128 bits of output 
at a time (more with wider AVX versions). If it takes 16 instructions to 
process one such block (and I predict that it will take less), that is 
only 1 instruction per byte of output, to be compared to a lookup table 
implementation that has a lower bound of 1 logical operation (a shift) 
AND 1 byte memory access per byte of output. This provides a very rough 
comparison of complexity (in terms of numbers of instructions) and 
performance to address your concern about how complex the SIMD 
implementation is.

As for "instruction cache having to restart": I have never read that in 
any optimization or ISA manual for the case of SSE or AVX; that seems to 
be a misconception of you. Can you point to a source?.

>> [3]: A lookup table implementation access the input data *and* the lookup
>> table;
>
> That's a really small table. Thirty years ago, it would have caused
> cache thrashing. Not so much now.

It is not about cache size but the required cache throughput. Using a 
lookup table means more reads than an arithmetical implementation (like 
I said: it requires reading the input data *and* the table), and data 
has to be read and written in very small blocks (1 byte for the lookup 
table, 6 bytes at most for the input data), which is generally slower 
than using bigger blocks.

>> replacing the lookup table with SIMD arithmetic reduces the demand on
>> memory (including cache) throughput.
>
> Does the AVX have that kind of table access? If you have a url for the
> relevant specs, I'd be interested.

AVX has gather support. You can look up the details in the Intel's or 
AMD's ISA manuals. However, _note that I am *not* talking about 
accessing a table with SIMD instructions._ I am completely replacing the 
lookup table with arithmetic done using SIMD instructions.

[toc] | [prev] | [next] | [standalone]

#160572

From	Joel Rees <joel.rees@gmail.com>
Date	2015-11-15 01:40 +0100
Message-ID	<quTwl-2Gu-1@gated-at.bofh.it>
In reply to	#160565

On Sun, Nov 15, 2015 at 12:22 AM, Mario Castelán Castro
<marioxcc.MT@yandex.com> wrote:
> El 13/11/15 a las 19:32, Joel Rees escribió:
>>
>> Do you use the -S option to get assembly language output to look at?
>
>
> Yes.
>
>> Yeah, SIMD instructions can also be used as a rather expensive
>> substitute for pure DMA. Expensive because they are used for more than
>> pure data move.
>
>
> What do you mean by "pure DMA" in this context?. If you mean "direct memory
> access", that is a concept that applies to peripherals who access memory
> directly, not the CPU.

When the CPU provides DMA instructions, it's DMA.
I don't remember how far Intel has gone with this, but many processors
implement string moves as full-fledged DMA, allowing the CPU to
continue processing other instructions in parallel.

Yeah, it's a bit tricky, and the compiler has to be a little
clairvoyant about pointers.

>> Those computations aren't as simple as you might think. Quite a bit of
>> branching, and the instruction cache having to restart,

Instruction queue. Sorry.

>> etc. It's
>> defnitely not SIMD, unless your SIMD has table lookup that can operate
>> independently in each data stream.

And I'm losing track of my thoughts there, as well.

> The computation does not require any branching (looping throughout the array
> not counted as part of the computation). Conditional expressions are
> evaluated using masks.

At the assembler level or compiler level?

> I have already implemented it that way processing 48
> input bits at a time that expand to 64 output bits, using 64 bits integers.

I can see that much for breaking the eight 6-bit fields out of a pair
of bytes, but the other stuff is puzzling me. In particular, pulling
six bytes out of memory is a bit field extraction, which is probably
not going to use AVX or whatever. And the parallel conversion from
binary to ascii is going to have half the processing units idle about
half the time in SIMD, and you can't predict which will be idle.

Idling processing units is not always bad, of course, if speeding up
the process is worth the cost of not letting the SIMD hardware work on
other things.

The reverse conversion has exceptional conditions, so it can only get
harder to parallelize.

> It's like SSE or AVX, but the distinction between vector elements is done
> completely in software;

So you are talking C level code?

> as far as hardware is concerned it's 64 bits logic
> and arithmetic. This implementation is like a "prototype" that I made so
> that I could actually evaluate how complex it is. It is simpler than I
> thought; with SSE or AVX it will be simpler still, since they have the
> separation between vector elements built in and have instructions dedicated
> to making masks and shuffling data.

If you know this much about the instructions, why are you wondering
about emulation? Why not just get (access to) the hardware?

> Also, SSE can process 96 bits of input that expand to 128 bits of output at
> a time (more with wider AVX versions). If it takes 16 instructions to
> process one such block (and I predict that it will take less), that is only
> 1 instruction per byte of output, to be compared to a lookup table
> implementation that has a lower bound of 1 logical operation (a shift) AND 1
> byte memory access per byte of output. This provides a very rough comparison
> of complexity (in terms of numbers of instructions) and performance to
> address your concern about how complex the SIMD implementation is.

And you don't actually need the hardware for this. In fact, you can
hand-assemble the SIMD instructions and get a good guess about how
well things will work.

> As for "instruction cache having to restart": I have never read that in any
> optimization or ISA manual for the case of SSE or AVX; that seems to be a
> misconception of you. Can you point to a source?.

Again, sorry for the brain gas. Instruction queue. Pipeline.
Restarting the pipeline.

But, if you are using masks, not in C level code, of course, but in
assembler, you are avoiding the restarts. You just have a varying
length no-op in your code, which might be a good trade-off, especially
since it would be (in hand assembled code on a CPU that can do it)
about four of eight instructions of effective no-op on expected
average.

>>> [3]: A lookup table implementation access the input data *and* the lookup
>>> table;
>>
>> That's a really small table. Thirty years ago, it would have caused
>> cache thrashing. Not so much now.

Sorry about mixing my thoughts without warning.

> It is not about cache size but the required cache throughput. Using a lookup
> table means more reads than an arithmetical implementation (like I said: it
> requires reading the input data *and* the table), and data has to be read
> and written in very small blocks (1 byte for the lookup table, 6 bytes at
> most for the input data), which is generally slower than using bigger
> blocks.

I was thinking out loud about dedicatable hardware that could lock the
table in cache. Sorry.

>>> replacing the lookup table with SIMD arithmetic reduces the demand on
>>> memory (including cache) throughput.
>>
>>
>> Does the AVX have that kind of table access? If you have a url for the
>> relevant specs, I'd be interested.
>
>
> AVX has gather support. You can look up the details in the Intel's or AMD's
> ISA manuals. However, _note that I am *not* talking about accessing a table
> with SIMD instructions._ I am completely replacing the lookup table with
> arithmetic done using SIMD instructions.

After I posted the previous, i had vague memories of some such, but I
couldn't remember the word "gather". Heh.

Anyway, the point is that you are moving your project forward, right?

-- 
Joel Rees

Be careful when you look at conspiracy.
Arm yourself with knowledge of yourself, as well:
http://reiisi.blogspot.jp/2011/10/conspiracy-theories.html

[toc] | [prev] | [next] | [standalone]

#160948

From	Mario Castelán Castro <marioxcc.MT@yandex.com>
Date	2015-11-22 00:00 +0100
Message-ID	<qxpiq-3kg-5@gated-at.bofh.it>
In reply to	#160572

El 14/11/15 a las 18:33, Joel Rees escribió:
> Anyway, the point is that you are moving your project forward, right?

Yes.

Now I have a working Base64 implementation using SSE. I developed it on 
my real computer since it has SSE support (up to SSE 4.2). I get a 
relative reduction of running time slightly above 50% (or above 100% 
speedup) compared to a lookup table version (which is faster than GNU 
Coreutils' version).

I will continue working on the details, possibly add AVX support using 
Bochs and maybe publish the code as a free software library (otherwise I 
would keep it unpublished; I do not make non free software).

Thanks for the help to everybody who replied to my thread.

[toc] | [prev] | [next] | [standalone]

#160542

From	Joel Rees <joel.rees@gmail.com>
Date	2015-11-14 02:00 +0100
Message-ID	<quxma-5g3-3@gated-at.bofh.it>
In reply to	#160330

On Mon, Nov 9, 2015 at 7:54 AM, Mario Castelán Castro
<marioxcc.MT@yandex.com> wrote:
> [...]
> joel.rees@gmail.com writes:
>>
>> The question being begged is this -- Do you really want to use AVX
>> enough to sign the Intel agreement that you can't read unless you
>> agree to it before you read it so you can download it and read it?
>>
>> It *is* a valid question, and I can't tell you the answer to that.
>> Maybe you can't answer that question yourself yet.
>
>
> No, I am not willing to use Intel's proprietary tools. In an earlier message
> in the same thread I said that I avoid proprietary software. That is one of
> the reasons of why I use Debian: It is easy to avoid the proprietary
> software.

Might I suggest you question (in addition to the questions about
actual performance benefits) whether dealing with Intel's hardware
licensing is significantly less onerous than dealing with their
software licensing. Also whether you can actually escape the software
licensing if you start developing to their hardware.

AVX is a minefield.

> -----
>
> Thanks to everybody who replied. I will probably use Bochs when time comes
> to port the algorithm to AVX. Right now I am writing and perfecting it in
> portable C, to have a base result against which to compare performance and
> complexity.
>
> Regards.
>

This is definitely the recommended course. Also check the time spent
in conversion with the time spent in data extraction and storing, etc.

-- 
Joel Rees

Be careful when you look at conspiracy.
Arm yourself with knowledge of yourself, as well:
http://reiisi.blogspot.jp/2011/10/conspiracy-theories.html

[toc] | [prev] | [next] | [standalone]

#160545

From	Mario Castelán Castro <marioxcc.MT@yandex.com>
Date	2015-11-14 02:20 +0100
Message-ID	<quxFw-5CH-3@gated-at.bofh.it>
In reply to	#160542

El 13/11/15 a las 18:50, Joel Rees escribió:
> On Mon, Nov 9, 2015 at 7:54 AM, Mario Castelán Castro
> <marioxcc.MT@yandex.com> wrote:
>> [...]
>> joel.rees@gmail.com writes:
>>>
>>> The question being begged is this -- Do you really want to use AVX
>>> enough to sign the Intel agreement that you can't read unless you
>>> agree to it before you read it so you can download it and read it?
>>>
>>> It *is* a valid question, and I can't tell you the answer to that.
>>> Maybe you can't answer that question yourself yet.
>>
>>
>> No, I am not willing to use Intel's proprietary tools. In an earlier message
>> in the same thread I said that I avoid proprietary software. That is one of
>> the reasons of why I use Debian: It is easy to avoid the proprietary
>> software.
>
> Might I suggest you question (in addition to the questions about
> actual performance benefits) whether dealing with Intel's hardware
> licensing is significantly less onerous than dealing with their
> software licensing. Also whether you can actually escape the software
> licensing if you start developing to their hardware.
>
> AVX is a minefield.

Minefield in what regard?. What do you mean by "Intel's hardware 
licensing"?.

If you mean licensing the patents that are required to *implement* the 
instruction set, bear in mind that I am not doing that: I am not 
designing nor implementing a CPU. AFAIK, no license is required to 
_write a program_ that uses some instruction set. I have never heard 
that a compiler, assembler, or program written partially in assembly had 
to acquire a license.

>> Thanks to everybody who replied. I will probably use Bochs when time comes
>> to port the algorithm to AVX. Right now I am writing and perfecting it in
>> portable C, to have a base result against which to compare performance and
>> complexity.
>>
>> Regards.
>>
>
> This is definitely the recommended course. Also check the time spent
> in conversion with the time spent in data extraction and storing, etc.

Sure. I have already made a trivial variation of my Base64 encoding code 
that does no conversion, only copies the data. I use this for 
comparison. I also compare speed against memcpy to have an idea of what 
the overhead against just copying is (taking into account that the data 
expands during encoding, some of the input data is duplicated into the 
output when using memcpy to make the comparison more fair).

Thanks.

[toc] | [prev] | [standalone]

csiph-web

How to write optimized code for an instruction set not supported by my computer?

Contents

#160237 — How to write optimized code for an instruction set not supported by my computer?

#160239

#160243

#160247

#160242

#160248

#160330

#160339

#160349 — Re: How to write optimized code for an instruction set not supported by my computer?

#160537

#160547

#160565

#160572

#160948

#160542

#160545