Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1258 > unrolled thread

optimizing compilers for low power design

Back to article view | Back to comp.compilers

Contents

  optimizing compilers for low power design idatarm@gmail.com - 2014-06-15 05:20 -0700
    Re: optimizing compilers for low power design Kaz Kylheku <kaz@kylheku.com> - 2014-06-15 15:43 +0000
      Re: optimizing compilers for low power design Ivan Godard <ivan@ootbcomp.com> - 2014-06-15 11:19 -0700
      Re: optimizing compilers for low power design <Pidgeot18@verizon.com.invalid> - 2014-06-15 18:58 -0500
      Re: optimizing compilers for low power design "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2014-06-16 12:11 +0100
        Re: optimizing compilers for low power design George Neuner <gneuner2@comcast.net> - 2014-06-18 04:44 -0400
          Re: optimizing compilers for low power design glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2014-06-20 18:13 +0000
          Re: optimizing compilers for low power design Ivan Godard <ivan@ootbcomp.com> - 2014-06-20 11:52 -0700
          Re: optimizing compilers for low power design Gene Wirchenko <genew@telus.net> - 2014-06-20 12:16 -0700
          Re: optimizing compilers for low power design George Neuner <gneuner2@comcast.net> - 2014-06-20 17:24 -0400
      Re: optimizing compilers for low power design Walter Banks <walter@bytecraft.com> - 2014-06-16 13:30 -0400
    Re: optimizing compilers for low power design andrewchamberss@gmail.com - 2014-06-20 05:03 -0700

#1258 — optimizing compilers for low power design

  Abstract: We describe an algorithm for optimizing compilers for low
  power design. The algorithm can be applied to almost any c compiler
  and in particular we target gcc compiler. The algorithm works by
  modifying optimization table lookup of gcc.  This works in theory. We
  think such an algorithm will be able save at least 20% power. We
  compare with alternatives. We show it that idea is viable and
  theoretically prove that it will account for about 20% power savings.
  Another 40% of the power savings will come from branch prediction
  techniques based on profile guided optimization. Similarly, we
  optimize for size, which will produce 10% power savings. We believe
  our program will save power up to 75%

http://www.davesinvoice.com/papers/low%20power%20design%201.pdf

[toc] | [next] | [standalone]

#1259

On 2014-06-15, idatarm@gmail.com <idatarm@gmail.com> wrote:
>   Abstract: We describe an algorithm for optimizing compilers for low
>   power design. The algorithm can be applied to almost any c compiler
>   and in particular we target gcc compiler. The algorithm works by
>   modifying optimization table lookup of gcc.  This works in theory. We

Instructions do not have a fixed power cost which can be measured by
repeating a long run of that instruction and then dividing.
It depends on their operands, and the complex state of the CPU (what
other instructions are in the pipeline before and after, caching, etc).
This approach might work on a very old processor, on which every instruction
had a predictable instruction count.

Furthermore, even if power cost is real, and you choose instructions according
to power cost, it's not going to work because instructions have to be primarily
chosen according to the computation that needs to be done.

For example, you can't choose a shift instruction if what you need is to add,
just because you think shift saves power.

To use a different instruction, you have to add numerous additional
instructions which massage the data and themselves have a power cost.
For instance, to use addition instead of subtraction, you have to negate an
operand, which is extra cycles.

The best way to save power is to just optimize for overall execution time, to
reduce how long the CPU has to be active.

>   think such an algorithm will be able save at least 20% power. We
>   compare with alternatives. We show it that idea is viable and
>   theoretically prove that it will account for about 20% power savings.
>   Another 40% of the power savings will come from branch prediction
>   techniques based on profile guided optimization. Similarly, we
>   optimize for size, which will produce 10% power savings. We believe
>   our program will save power up to 75%

Percentages do not add. Combining 20%, 40% and 10% means doing this:

100 * (1 - 0.8 * 0.6 * 0.9) = 56.8%.

I.e. a 20% reduction, 40% reduction and a further 10% reduction
add up to a 56.8% reduction, not 75%. (Where are you getting the extra 5% from,
by the way?  Even under the incorrect arithmetic combination, your percentages
only add to 70%, not 75%.)

Profile-guided branch optimization, and optimizing for size, are not your
inventions; these are things that can be done today with existing compilers.
You cannot claim that it is "your program".

Optimizing for size almost certainly conflicts with choosing instructions for
other constraints like speed or power.  That is to say, if a program is
optimized for size, then further optimizing it for power based on instruction
power cost is probably much more difficult with a poorer yield, and vice versa.
You will never reap the best of both yields.

Your paper's reference [1], "A Guide to LaTeX" is inappropriate to your
topic and suggests that you're trying to inflate your reference section.  If
you're going to do this this, bury the questionable reference in the
middle of the list; do not begin the list with one.

You have a typographical problem.  Throughout the paper, you cite your
references, but there is no number in the square brackets; they have come out
as []. For instance in VIII you have " For more concrete proof, look at work by
[] ...".

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

#1260

On 6/15/2014 8:43 AM, Kaz Kylheku wrote:
> On 2014-06-15, idatarm@gmail.com <idatarm@gmail.com> wrote:
>>    Abstract: We describe an algorithm for optimizing compilers for low
>>    power design. The algorithm can be applied to almost any c compiler
>>    and in particular we target gcc compiler. The algorithm works by
>>    modifying optimization table lookup of gcc.  This works in theory. We
>

<snip>

< An excellent critique omitted. >

Only one addition: the amount of active power (switching gates) and
the amount of passive power (leakage) varies by fab process, but as a
rule the proportion of the passive part increases with smaller feature
sizes.  Smaller than roughly the 28nm node, actual execution of ops
increasingly comes for free.

However, leakage is (roughly) proportional to area or equivalently, gate
count), so by far the greatest power saving available derives from
reducing area/count for a given amount of computation. In a modern OOO
chip, the great bulk of the area/count is devoted to figuring out what
you are going to do next, getting everything ready to do it, and then
dealing which what you have done. The amount spent in actually doing it
(in an adder, for example) is near trivial. So changing op A into op B
doesn't win anything, because the hardware surrounding A or B dominates
the power, and even if B uses less active power than A the hardware to
do A is still there leaking away.

This is why so much has shifted to in-order architectures: they have
much less area/power required around the functional units. The problem
with them is that they cannot achieve the ILP of an OOO architecture;
all that cruft around the adders really does do something, it's just
expensive. Exchanging ops won't help; you have to do something
architectural, like our Mill, to get the ILP of OOO and the area/power
of a DSP.

Ivan
[Are we on the verge of reinventing VLIW? -John]

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

#1262

On 6/15/2014 10:43 AM, Kaz Kylheku wrote:
> On 2014-06-15, idatarm@gmail.com <idatarm@gmail.com> wrote:
>>    Abstract: We describe an algorithm for optimizing compilers for low
>>    power design. The algorithm can be applied to almost any c compiler
>>    and in particular we target gcc compiler. The algorithm works by
>>    modifying optimization table lookup of gcc.  This works in theory. We
>
> Instructions do not have a fixed power cost which can be measured by
> repeating a long run of that instruction and then dividing.
> It depends on their operands, and the complex state of the CPU (what
> other instructions are in the pipeline before and after, caching, etc).
> This approach might work on a very old processor, on which every instruction
> had a predictable instruction count.

I see it as plausible that different functional units can take
usefully different power to compute (i.e., using x86 SSE instructions
versus the x87 instruction set, or using vectorized versus
non-vectorized instructions). Even then, though, I consider it only an
a priori plausible event--you'd need to provide experimental evidence
that it actually occurs in practice before continuing.

> Percentages do not add.

Were that the only serious error of this paper. The percentages
themselves seem to be literally conjured out of thin air.

> Your paper's reference [1], "A Guide to LaTeX" is inappropriate to your
> topic and suggests that you're trying to inflate your reference section.  If
> you're going to do this this, bury the questionable reference in the
> middle of the list; do not begin the list with one.

The other 4 references are equally irrelevant. Two of them are
self-citations of earlier work on what appears to be waveform pattern
generation for electrical circuits and the other two may be culled from
the references of those problems. In contrast, a typical PL paper would
contain a page of references or more.

> You have a typographical problem.

The grammatical mistakes in the paper reached the threshold of "actively
distracting" for me.

Curious, I decided to see what other papers might be found, given that
the URL contains a papers folder.
...

Unfortunately, this appears to be the most logically cohesive paper of
the lot. The more I read, the more I got the feeling that the author is
very much outside of his capabilities in this line of work.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

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

#1263

Kaz,

> Furthermore, even if power cost is real, and you choose instructions according
> to power cost, it's not going to work because instructions have to be primarily
> chosen according to the computation that needs to be done.

There has been some interesting work on making power minimization
a constraint during instruction scheduling.

A surprising percentage of power is consumed when a signal changes from
0 to 1 or from 1 to 0.  So the idea is to arrange instruction order to
minimise the number of transitions at each bit position in an
instruction sequence.
[CMOS only uses power when it switches, so I'd think approximately all
of the power would be consumed when a signal changes.  The idea of
Gray coded instruction streams is weirdly appealing. -John]

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

#1266

On Mon, 16 Jun 2014 12:11:32 +0100, "Derek M. Jones"
<derek@_NOSPAM_knosof.co.uk> wrote:

>A surprising percentage of power is consumed when a signal changes from
>0 to 1 or from 1 to 0.  So the idea is to arrange instruction order to
>minimise the number of transitions at each bit position in an
>instruction sequence.
>
>[CMOS only uses power when it switches, so I'd think approximately all
>of the power would be consumed when a signal changes.  The idea of
>Gray coded instruction streams is weirdly appealing. -John]

I'm mostly a software person, so this may be way off base.
However ...

For Gray coding instructions to be effective, most instructions would
have to offer multiple choices for their encoding.  Certainly for the
most commonly used instructions and probably there would need to be at
least several choices of encoding.

ISTM then that the decoder becomes n-ways wider at each decision step,
and somewhat deeper [though maybe not twice] due to requiring
additional combining/filtering steps.  So fetch to execute latency
would suffer and materially affect [already problematic] branching
performance.

Moreover, I would think that to make this work best you'd also need to
use fixed sized instructions externally so that there is no additional
pre-decode penalties for locating instruction boundaries, aligning
bits, needing extra fetches for instructions that span fetch lines,
etc.  You want to be able to just shift and drop each instruction
directly into the decoder.  But fixed size instructions would put
additional fetch pressures on the memory system.

On the software side, compilation becomes combinatorially more
expensive.  You might save some CPU power at execution, but ISTM that
any savings from the CPU would be minimal because memory and cache
power are unaffected:  I don't see any reasonable possibility to
minimize bit transitions from fetch line to fetch line, or farther
across cache address strides (which I think would help only with a
direct mapped cache anyway).


comp.compilers probably is not the right forum, but perhaps someone
who has CPU design experience can *briefly* speak to the hardware
aspect of this idea.  Or we can take it to comp.arch.

George
[The Gray coding was mostly a joke. You're right, the circumstances
in which it would be useful are unrealistically limited. -John]

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

#1269

George Neuner <gneuner2@comcast.net> wrote:
> On Mon, 16 Jun 2014 12:11:32 +0100, "Derek M. Jones"

(snip)
>>A surprising percentage of power is consumed when a signal changes from
>>0 to 1 or from 1 to 0.  So the idea is to arrange instruction order to
>>minimise the number of transitions at each bit position in an
>>instruction sequence.

>>[CMOS only uses power when it switches, so I'd think approximately all
>>of the power would be consumed when a signal changes.  The idea of
>>Gray coded instruction streams is weirdly appealing. -John]

And off-chip lines require much more current than on-chip, so you
really only need to consider the external address and data bus.

If you really want to do this, you want a Gray coded program counter,
and instructions appropriately placed in memory.

> I'm mostly a software person, so this may be way off base.
> However ...

> For Gray coding instructions to be effective, most instructions would
> have to offer multiple choices for their encoding.  Certainly for the
> most commonly used instructions and probably there would need to be at
> least several choices of encoding.

If I remember right, in the early 8080 days, people figured out some
bit patters that were decodable as instructions, but were not listed
officially. That is, "don't care" cases for the instruction decode
logic.  Some of those might be appropriate bit patters.

> ISTM then that the decoder becomes n-ways wider at each decision step,
> and somewhat deeper [though maybe not twice] due to requiring
> additional combining/filtering steps.  So fetch to execute latency
> would suffer and materially affect [already problematic] branching
> performance.

That is what I thought at first, but the current for off-chip drivers
is so much higher, that you might as well only count them.

> Moreover, I would think that to make this work best you'd also need to
> use fixed sized instructions externally so that there is no additional
> pre-decode penalties for locating instruction boundaries, aligning
> bits, needing extra fetches for instructions that span fetch lines,
> etc.  You want to be able to just shift and drop each instruction
> directly into the decoder.  But fixed size instructions would put
> additional fetch pressures on the memory system.

That, or you also have to count the other bytes of each instruction.
If you had PDP-11 like instructions, with a 16 bit opcode, and then
optional immediate data words, you would include those data words.
Words addressing memory locations could be optimized in the same
way. It is a little harder for data.

> On the software side, compilation becomes combinatorially more
> expensive.  You might save some CPU power at execution, but ISTM that
> any savings from the CPU would be minimal because memory and cache
> power are unaffected:  I don't see any reasonable possibility to
> minimize bit transitions from fetch line to fetch line, or farther
> across cache address strides (which I think would help only with a
> direct mapped cache anyway).

You either don't have off-chip cache, or consider the cache as the
primary source of bits. As above, only off-chip bits need to be
considered.

> comp.compilers probably is not the right forum, but perhaps someone
> who has CPU design experience can *briefly* speak to the hardware
> aspect of this idea.  Or we can take it to comp.arch.

> [The Gray coding was mostly a joke. You're right, the circumstances
> in which it would be useful are unrealistically limited. -John]

It would only make sense for a processor that was going to be
executing the same code for a very long time, such as one in space.

Only last week, in a discussion on another newsgroup, I was
remembering the ICT, Integer Cosine Transform.

The ICT was invented for the Galileo spacecraft to minimize the
time needed to compress image data. The CDP1802 (or radiation
hard version of it) has no multiply instruction, so they wrote
a transform where the coefficients are selected to minimize the
bits that are '1'. That speeds up the shift and add multiplication.

Speeding up the encoding can be done at the expense of slowing down
decoding, which is done on earth.

http://tmo.jpl.nasa.gov/progress_report/42-115/115j.pdf

-- glen

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

#1270

On 6/18/2014 1:44 AM, George Neuner wrote:
> On Mon, 16 Jun 2014 12:11:32 +0100, "Derek M. Jones"
> <derek@_NOSPAM_knosof.co.uk> wrote:
>
>> A surprising percentage of power is consumed when a signal changes from
>> 0 to 1 or from 1 to 0.  So the idea is to arrange instruction order to
>> minimise the number of transitions at each bit position in an
>> instruction sequence.
>>
>> [CMOS only uses power when it switches, so I'd think approximately all
>> of the power would be consumed when a signal changes.  The idea of
>> Gray coded instruction streams is weirdly appealing. -John]
>
> I'm mostly a software person, so this may be way off base.
> However ...
>
> For Gray coding instructions to be effective, most instructions would
> have to offer multiple choices for their encoding.  Certainly for the
> most commonly used instructions and probably there would need to be at
> least several choices of encoding.
>
> ISTM then that the decoder becomes n-ways wider at each decision step,
> and somewhat deeper [though maybe not twice] due to requiring
> additional combining/filtering steps.  So fetch to execute latency
> would suffer and materially affect [already problematic] branching
> performance.

True if you are parsing instruction-by-instruction, but there are ways
around that, see millcomputing.com/docs/encoding. In a wide-issue
machine (where the instruction contains several operations to issue in
parallel, like a VLIW, or any of several other less common schemes), it
is possible to group the individual operations by natural encoding size.
The problem then reduces to isolating the blocks, and the cost of that
is amortised over the contained operations rather than being repeated
for each. This is not frequency-based Gray coding, but nevertheless
produces a much more compact encoding that the usual while at the same
time being cheap to parse; experiment (unpublished) shows the encoding
to be within a bit of Gray code

> Moreover, I would think that to make this work best you'd also need to
> use fixed sized instructions externally so that there is no additional
> pre-decode penalties for locating instruction boundaries, aligning
> bits, needing extra fetches for instructions that span fetch lines,
> etc.  You want to be able to just shift and drop each instruction
> directly into the decoder.  But fixed size instructions would put
> additional fetch pressures on the memory system.

The citation above addresses these issues too.

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

#1272

On Wed, 18 Jun 2014 04:44:43 -0400, George Neuner
<gneuner2@comcast.net> wrote:

[snipped serious reply]

>[The Gray coding was mostly a joke. You're right, the circumstances
>in which it would be useful are unrealistically limited. -John]

     It was a good joke.  Mr. Neuner's reply was an interesting
exercise in logic.

Sincerely,

Gene Wirchenko

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

#1273

On Wed, 18 Jun 2014 04:44:43 -0400, George Neuner
<gneuner2@comcast.net> wrote:

>[The Gray coding was mostly a joke. You're right, the circumstances
>in which it would be useful are unrealistically limited. -John]

I understood that you meant to be funny, but the idea itself isn't.

For a number of reasons I can't see it being adopted generally - but,
if it worked well enough, it would be worth the effort for very low
power (battery) applications and maybe also for super-computer
applications where power and cooling are ever increasing expenses.

George

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

#1264

Kaz Kylheku wrote:

> On 2014-06-15, idatarm@gmail.com <idatarm@gmail.com> wrote:
> >   Abstract: We describe an algorithm for optimizing compilers for low
> >   power design. The algorithm can be applied to almost any c compiler
> >   and in particular we target gcc compiler. The algorithm works by
> >   modifying optimization table lookup of gcc.  This works in theory. We
>
> Instructions do not have a fixed power cost which can be measured by
> repeating a long run of that instruction and then dividing.
> It depends on their operands, and the complex state of the CPU (what
> other instructions are in the pipeline before and after, caching, etc).
> This approach might work on a very old processor, on which every instruction
> had a predictable instruction count. ...

> The best way to save power is to just optimize for overall execution time, to
> reduce how long the CPU has to be active. ...

A long time ago we wrote a compiler that optimized for minimum power
consumption. The application was a data logger that needed to be run
on battery power for about 14 months unattended. In what can basically
be described as a bad environment.

We did several things.

1) In the absence of hard data we modelled the processor instruction
set on the number of memory access to ROM and the two types of RAM we had
available.
The RAM was a block of RAM internal to the processor and external memory.

2) The external memory could be significantly powered down into a sleep mode
where it retained information but could no be accessed. The external RAM mode
was processor controlled.

3) The processor had a sleep mode that we eventually did not use. We added
a clock chip that was set up to power up and reset the processor. The processor
internal memory could be set-up to retain information.

4) There are a lot of non processor items that we also did. Unused inputs and
outputs we put into their lowest power mode. Pull-ups and pull down resistors
were all evaluated for their effect on power consumption.

5) As Derek Jones pointed out I/O transitions cost power we counted them
and brought the number out as static metric

5) Processor clock speed was a complex combination of time needed to
execute and on time for the rest of the electronics.

6) The compiler looked at alternative sequences and the power resources they
used. (Different from optimization of the instruction set in this was more data
flow optimization) It looked at minimizing the total time needed for the external
memory for example.

7) Software design played a major role. When this project was first developed
it would run for between 2 and 3 months. In the end after what was essentially
all software changes it was reliably running for 16 months.

w..

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

#1267

"The best way to save power is to just optimize for overall execution time, to
reduce how long the CPU has to be active."

Perhaps not entirely true, but it may require the compiler to know
more about the whole system and is able disable parts of the system it
knows aren't necessary by code analysis. Not that I have any real data
to back that up.

This paper does seem to have some problems though.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web