Questions about how to optimise a program's performance, both manually and automatically, e.g. in compilers.

learn more… | top users | synonyms

0
votes
0answers
45 views

A Fast Algorithm to Approximately Solve a Modified Version of The Thomson Problem

The problem I'm trying to solve is the same as the Thomson Problem except that the objective isn't to minimize $$ U(N) = \sum_{i < j} \frac{1}{r_{ij}}, $$ given $r_{ij} = |\mathbf{r_i} - ...
3
votes
2answers
39 views

Loop-invariant code motion with unsafe operations

There are well-known algorithms LICM, and they work well. Unfortunately, there are certain cases when these optimizations can cause runtime failures with code that was initially correct. Consider the ...
0
votes
0answers
30 views

Implementing/approximating Belady's OPT for multithreaded environments (papers?)

I have the memory reference string for a multithreaded application and want to run this through a simulator which implements/approximates Belady's OPT page replacement algorithm. But what is the best ...
1
vote
0answers
45 views

Amdahl “validity of the single processor approach”

The following is Figure 1 in Gene M. Amdahl's "Validity of the single processor approach to achieving large scale computing capabilities" (1967) (PDF): The text describes this as representing the ...
3
votes
0answers
71 views

How to compute an optimally cost-effective cache strategy?

I am looking for advice in the following optimization problem. I have a website (system) that receives database updates later returned in queries made to the same system. In order to speed up the ...
2
votes
2answers
103 views

Chaitin's elegant programs

I need help to understand Chaitin's elegant program proof. An elegant program is the shortest program that produces a given output. Here is the proof: Construct a program $B$ that takes as input ...
1
vote
1answer
65 views

Difference between symbolic execution and reachability analysis

Now I am confused about symbolic execution (SE) and reachability analysis (RA). As I know, SE uses symbols to execute some code to reach each branch with branch conditions. And RA can be used to find ...
12
votes
1answer
216 views

Do fully optimizing compilers for terminating programs exist?

In Andrew W. Appel's book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and ...
1
vote
3answers
164 views

Fastest Algo to separate the 0s and 1s [closed]

Suppose, I have an array of length 100. I have 0s at some positions and 1s at some other positions. What is the fastest method by which I can separate the 0s and 1s, so that we get all the 0s at the ...
3
votes
1answer
1k views

Using Amdahl's law how do you determine execution time after an improvement?

Speeding up a new floating-point unit by 2 slows down data cache accesses by a factor of 2/3 (or a 1.5 slowdown for data caches). If old FP unit took 20% of program's execution time and data cache ...
0
votes
1answer
75 views

Using Loop Dependence analysis for vectorization

How exactly Loop Dependence Analysis helps in vectorization ? Are there any standard rules of safety criterias for parallizing such loops ?
2
votes
1answer
74 views

Benefit of Backward Pass at compile time

We collect most of the information about possible compiler optimizations during forward pass. Is it possible to utilize the information collected in forward pass in a backward pass so as to perform ...
5
votes
1answer
107 views

Are compilers able to detect alternating accesses to arrays and interleave them in memory?

Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this: ...
5
votes
1answer
88 views

Dataflow framework for global analysis: Why meet, then apply?

In Chapter 9 of the Dragon Book, the authors describe the dataflow framework for global analysis (described also in these slides). In this framework, an analysis is defined by a set of transfer ...
7
votes
1answer
375 views

Micro-optimisation for edit distance computation: is it valid?

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: ...
6
votes
0answers
128 views

Optimizing order of graph reduction to minimize memory usage

Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used. That is, given ...