# Should AI Optimize Your Code? A Comparative Study of Current Large Language
Models Versus Classical Optimizing Compilers

Miguel Romero Rosas<EMAIL_ADDRESS>0009-0003-7145-3429 ,  Miguel Torres
Sanchez<EMAIL_ADDRESS>0009-0003-6209-9675 University of
DelawareNewarkDelawareUSA19713 and  Rudolf Eigenmann  University of
DelawareRono-HillsNewarkDelawareUSA

(2024; 30 May 2024)

###### Abstract.

In the contemporary landscape of computer architecture, the demand for
efficient parallel programming persists, needing robust optimization
techniques. Traditional optimizing compilers have historically been pivotal in
this endeavor, adapting to the evolving complexities of modern software
systems. The emergence of Large Language Models (LLMs) raises intriguing
questions about the potential for AI-driven approaches to revolutionize code
optimization methodologies.

This paper presents a comparative analysis between two state-of-the-art Large
Language Models, GPT-4.0 and CodeLlama-70B, and traditional optimizing
compilers, assessing their respective abilities and limitations in optimizing
code for maximum efficiency. Additionally, we introduce a benchmark suite of
challenging optimization patterns and an automatic mechanism for evaluating
performance and correctness of the code generated by such tools. We used two
different prompting methodologies to assess the performance of the LLMs –
Chain of Thought (CoT) and Instruction Prompting (IP). We then compared these
results with three traditional optimizing compilers, CETUS, PLUTO and ROSE,
across a range of real-world use cases.

A key finding is that while LLMs have the potential to outperform current
optimizing compilers, they often generate incorrect code on large code sizes,
calling for automated verification methods. Our extensive evaluation across 3
different benchmarks suites shows CodeLlama-70B as the superior optimizer
among the two LLMs, capable of achieving speedups of up to 2.1x. Additionally,
CETUS is the best among the optimizing compilers, achieving a maximum speedup
of 1.9x. We also found no significant difference between the two prompting
methods: Chain of Thought (Cot) and Instructing prompting (IP).

Automatic parallelization, Large Language Models, Compilers

††copyright: acmlicensed††journalyear: 2024††doi: XXXXXXX.XXXXXXX††conference:
March 01–05, 2025; Las Vegas, NV; ††isbn: 978-1-4503-XXXX-X/18/06††ccs:
Computing methodologies Parallel programming languages††ccs: Computing
methodologies Artificial intelligence††ccs: Software and its engineering
Software verification and validation

##  1\. Introduction

The need for developing and optimizing parallel programs is paramount
(Leiserson et al., 2020). Optimizing compilers have long been one of the
pillars of creating parallel code, evolving continuously to meet the growing
complexity of modern programs. However, despite all advancements, current
compilers still do not achieve the necessary performance to be true
alternatives to manual parallelization (Bhosale et al., 2022).

The dawn of Large Language Models (LLMs), such as GPT and CodeLlama raises a
fundamental question: Can AI-driven models revolutionize the way we approach
code optimization? These models paint an appealing horizon for code
optimization and parallel code generation (Pornmaneerattanatri et al., 2024).
Among several LLMs, we chose to use GPT4.0 from OpenAI (OpenAI, [n. d.]) and
CodeLlama-70B (META, [n. d.]) from META, as these represent the state-of-the-
art and thus offer the promise of efficient code generation (Liu et al.,
2023).

Our study compares three state-of-the-art optimizing compilers, CETUS (Bae et
al., 2013), PLUTO (Bondhugula et al., 2008a) and ROSE (Quinlan and Liao, 2011)
against the two LLMs for parallel code optimization. We evaluate their
capacity to serve as Automatic Optimization Tools (AOTs).

One of the challenges in using LLMs for code generation is the lack of
correctness guarantee. To address this critical gap, we developed a mechanism
for automatic validation of the generated programs. The mechanism enables LLMs
to be used as AOTs and facilitates the comprehensive evaluation of these
models. The mechanism can also serve as a general instrument facilitating the
use of unsafe optimizations. To the best of our knowledge this is the first
such mechanism, enabling the automatic use of optimizations that do not ensure
correctness.

In our evaluation, we are specifically interested in code patterns that
challenge current automatic optimization tools and in the ability of LLM-based
AOTs to overcome these challenges. To this end, we have developed a benchmark
suite of such patterns. Next to a comprehensive evaluation, the suite also
allows us to identify areas for improvement in parallel code optimization.

This paper makes the following contributions:

  * •

We present a comparative study of LLMs and traditional optimizing compilers,
utilizing study cases from real-world applications, such as the NAS Parallel
Benchmarks Suite (NPB) v3.3 (Bailey et al., 1991), the POLYBENCHMARK (PB)
Suite v4.2 (Yuki and Pouchet, [n. d.]), and other relevant programs.

  * •

We introduce an automated mechanism for validating the correctness and
performance of AOT-generated code.

  * •

We present a Parallel Computing Challenge Benchmark suite (PCB) v1.0,
comprising 20 use cases for evaluating the capabilities of AOTs.

This paper is organized as follows: Section 2 explores strengths and
limitations of our chosen optimizing compilers and LLMs. Section 3 describes
our environment for evaluating automatic optimization tools and presents the
Parallel Computing Challenge Benchmark suite (PCB). Section 4 evaluates the
capabilities of our LLMs and optimizing compilers on challenging code
patterns, followed by the discussion of related work in Section 5 and
conclusions 6.

##  2\. LLMs vs Traditional Compilers, Strengths and Limitations

Current optimizing compilers exhibit a mix of challenges and opportunities
(Monsifrot et al., 2002; Zhao et al., 2005; Li et al., 2014). They include
limitations of static analysis, hampering the identification of optimization
opportunities, and the complexity of deciding on best optimization patterns
for maximum program performance (Barakhshan and Eigenmann, 2023b). It is in
this context that the power of LLMs emerges, offering new potential ways to
approach program optimization.

Large Language Models have garnered significant attention in recent years
owing to their statistical understanding of programs, offering suggestions for
code generation, and facilitating software creation (Li et al., 2023) (Li et
al., 2022) (Achiam et al., 2023) (Chen et al., 2021). While LLM-generated
software has demonstrated success in many applications, recent studies have
highlighted the limitations in capturing crucial aspects of linguistic meaning
and understanding semantic properties of the user’s prompt (Asher et al.,
2023).

Despite these limitations, recent studies indicate that Large Language Models
excel in programming tasks such as code generation, issue fixing, and code
completion (Valero-Lara et al., 2023). This proficiency is largely attributed
to the vast amount of data available on platforms such as GitHub, enabling
effective training. However, even though LLMs can generate effective code, the
lack of correctness guarantees make them unsuitable for many code optimization
approaches (Shypula et al., 2023; Kadosh et al., 2023; Chen et al., 2023;
Nichols et al., 2023).

In pursuit of the question asked in the Introduction Can AI-driven models
revolutionize the way we approach code optimization?, this paper investigates
in what situations Large Language Models perform well and where not. To this
end, we have developed an environment for comparing the optimization
capabilities of LLMs with those of classical optimizing compilers, including
the creation of an automated code verification mechanism and a benchmark suite
of code challenge patterns. The next section describes this environment.

##  3\. An Environment for Evaluating Automatic Optimization Tools

Recall that the lack of a methods for verifying the correctness of LLM-
generated code make it difficult to compare such tools with other AOTs.
Section 3.1 introduces a novel method and environment called PCAOT
(Performance and Correctness Evaluation of Automatic Optimization Tools) that
overcomes this limitation. Additionally, we have created the Parallel
Challenge Patterns Benchmark (PCB) suite v1.0 with 20 distinct use cases. The
suite and the challenge patterns are discussed in Section 3.2.

###  3.1. Evaluation and Verification

Our approach entails selecting two Large Language Models (LLMs), GPT-4.0 and
CodeLlama-70B, and evaluating their code optimization capabilities. The
results are then compared with three different optimizing compilers, CETUS,
PLUTO and ROSE. For engaging the LLMs, we use two prompting strategies,
descibed next.

####  3.1.1. Prompting Strategies

We explored two different prompts associated with utilizing Large Language
Models for High-Performance Computing optimization tasks. Initially, we
employed instruction prompting (IP) (Mishra et al., 2021) (Gupta et al.,
2022). Additionally, we employed Chain of Thought (CoT) within these Large
Language Models. Recent studies indicate that Chain of Thought prompting
enhances performance across a spectrum of arithmetic, commonsense, and
symbolic reasoning tasks, making it well suited for assessing domain-specific
knowledge such as Parallel Computing (Wei et al., 2022).

CETUS, PLUTO, and ROSE translate C programs to equivalent C code annotated
with OpenMP parallel directives. Incorporating OpenMP into the prompts
facilitates the comparison of the code generated by LLMs and these compilers.
We chose the following prompts:

  * •

Instructing (IP) - ”Given the program below, improve its performance using
OpenMP”.

  * •

CoT - ”Given the C program below, think of a way how to optimize its
performance using OpenMP”

The distinction between these two types of prompts lies in their approach to
guiding the model’s reasoning process. Instructing prompts provide a direct
and clear directive, resulting in the immediate production of an optimized
program version. In contrast, Chain of Thought prompts enable the model to
break down the task into multiple steps, allowing for iterative refinement
before generating an optimized program version. Instances of guidance the
model in this process are: ”Think of a way…”, ”propose…”, ”give a potential
strategy…” (Shypula et al., 2023).

For the optimizing compilers CETUS, PLUTO, and ROSE, we used the default set
of parameters, representing the known, safe optimization methods. Note that,
while experimenting with optimization options could potentially yield improved
performance, doing so is beyond the scope of this paper. Our environment for
evaluating the five AOTs comprises three phases: Preparation, Optimization,
and Validation. Figure 1 illustrates this architecture.

Figure 1. Architecture of the PCAOT Environment.

####  3.1.2. Preparation Phase

LLMs have shown to have limitations to process programs with large code sizes
(OpenAI, [n. d.]) (META, [n. d.]). Hence, our LLM evaluation focuses on
section-level optimizations. The preparation phase identifies the sections
within the source code to experiment with. Each such section is manually
enclosed with #pragma experimental section start and #pragma experimental
section end, as illustrated in Figure 2. The impact of code size on the
performance of the LLMs will be discussed in Section 4.2.

      1: #pragma experimental start
      2: for (k=0; k<=(grid_points[2]-1); k ++ )
      3:  {
      4:    for (j=0; j<=(grid_points[1]-1); j ++ )
      5:    {
      6:        for (i=0; i<=(grid_points[0]-1); i ++ )
      7:        {
      8:            for (m=0; m<5; m ++ )
      9:            {
      10:                rhs[k][j][i][m]=forcing[k][j][i][m];
      11:            }
      12:        }
      13:    }
      14:}
      15: #pragma experimental end

Figure 2. Experimental section instrumentation. Example is from subroutine
Compute_rhs of the NPB Application CG.

For our experiments we made used of a tool called CaRV (Capture, Replay, and
Validate), which enables users to experiment with sections of large
applications. It facilitates the comparison of individual program sections
before and after optimizations, assessing their efficiency and accuracy
(Barakhshan and Eigenmann, 2023a). CaRV does so using a selective
checkpointing method, based on the identified program states at the beginning
and end of an experimental section.

The preparation phase generates a new program version that is instrumented in
a way that allows the optimized program section to be run independently and
compared against the captured end state of the original program. Both the
original and instrumented program versions are passed on to the optimization
phase.

####  3.1.3. Optimization Phase

This phase sends the experimental section with the prompts to the two LLMs to
obtain the optimized versions. The resulting code is then inserted into the
instrumented program. The original code is also sent to the three compilers,
CETUS, PLUTO and ROSE. This process generates a total of 16 program versions,
for the five AOTs (two LLMS, two different prompts, three requests per prompt,
three optimizing compilers plus the serial program) The next phase executes
and validates these versions.

####  3.1.4. Validation Phase

The Validation phase executes each version of the experimental section
individually. The LLM-generated versions are then compared with the original,
serial program versions, using the CaRV checkpoints. This process verifies the
values of all relevant, ”live” variables at the end of the LLM-optimized
program section against the corresponding values in the original program. The
execution time is measured as well and compared to that of the original
program section.

###  3.2. Parallel Computing Challenge Pattern Benchmark Suite v1.0 (PCB)

This new Benchmark suite comprises 20 distinct use cases, each presenting one
of six challenging scenarios encountered by optimizing compilers (Barakhshan
and Eigenmann, 2023b). A number of patterns are included in the PCB suite,
testing the optimizers in their ability to

  * •

parallelize outermost loops (PO),

  * •

parallelize loops with function calls (PF),

  * •

form parallel regions enclosing multiple parallel loops (PR),

  * •

avoiding load imbalance through dynamic scheduling (DS),

  * •

parallelizing array reductions (PA),

  * •

eliminate barrier synchronizations using NOWAIT clause (NW).

Given the challenges traditional optimizing compilers face in handling these
patterns (Barakhshan and Eigenmann, 2023b) (Prema et al., 2017), an important
question is:  Can LLMs identify these patterns and perform the requisite
optimizations? The following paragraphs explain the involved program patterns:

##### Parallelizing Outermost Loops

This pattern involves identifying and parallelizing the outermost loops in a
program section, which often represent significant computational tasks.
Parallelizing these loops can improve performance by distributing the number
of iterations across multiple processors or threads. Running the outer loop in
parallel typically results in lower overhead compared to parallelizing the
inner loop, as inner parallelism increases the number of times of starting and
ending parallel activities. This pattern poses a challenge because real-world
scenarios often contain loops with complex expressions that prove too
difficult for compilers’ static analysis capabilities. Automatic optimizers
often success in parallelizing the inner loops only. Figure 3 illustrates this
situation.

        1: int sum
        2: for (int i = 0; i < size; ++i) {
        3:   for (int j = 0; j < size; ++j) {
        4:      for (int k = 0; k < size; ++k) {
        5:       #pragma omp parallel for
        6:       for (int l = 0; l < size; ++l) {
        7:         int position =i*size * size * size + j * size ;
        8:         int index = position  * size + k * size + l;
        9:         sum += data[indices[index]];
        10:        }
        11:     }
        12:   }
        13: }

Figure 3. Parallelizing the outermost loop pattern in an example loop from the
PCB v1.0. Compilers tend to parallelize the inner-most loop, due to the
irregular data accesses in code line #9. Doing so incurs the overhead of
starting the parallel region $size^{3}$ . Parallelizing the outermost loop
would eliminate this overhead.

##### Parallelizing Loops with Function Calls

Parallelizing loops with function calls presents a significant challenge for
optimizing compilers, as many optimization techniques do not operate
interprocedurally. A special situation is the presence of calls to side-
effect-free functions (functions that only modify their parameters), which
only require the optimizer to determine the independence of the variables
passed as function parameters. Loops with such functions can be parallelized.
Figure 4 illustrates this situation.

        1: int size = 1000;
        2: int result[size][size];
        3: for (int i = 0; i < size; i++) {
        4:    for (int j = 0; j < size; j++) {
        5:        for (k = 0; k < size; k++){
        6:            result[i][j][k] = compute(i, j, k);
        8:            }
        9:    }
        10: }
           .
           .
           .
        13: /* Side effect free fuction call*/
        14: int compute(int x, int y, int k) {
        15:    int result = 0;
        16:       for (int i = 0; i < x; i++) {
        17:        result += (x + y + k) * i;
        20:        return result;
        21:    }
        22: }

Figure 4. Parallelizing Loops with Function Calls pattern in an example loop
from the PCB v1.0. Function compute is side effect free. The loop in line #3
can be parallelized.

##### Parallel Regions Enclosing Multiple Parallel Loops

Current optimizing compilers are limited to optimizing loops individually and
cannot apply optimizations across a set of loops within a parallel region. By
enclosing multiple parallel loops within a single parallel region, the
overhead associated with starting and ending each parallel loop separately is
reduced. Figure 5 illustrates this pattern.

        1: int array[1000];
        2: int result[1000];
        3:  // Initialize array
        4:    for (int i = 0; i < NUM_ELEMENTS; i++) {
        5:        array[i] = i;
        6:    }
        7:
        8:   #pragma omp parallel
        9: {
        10:    #pragma omp parallel for
        11:    for (int i = 0; i < NUM_ELEMENTS; i++) {
        12:        result[i] = array[i] * 2;
        13:    }
        14:
        15:    #pragma omp parallel for
        16:    for (int i = 0; i < NUM_ELEMENTS; i++) {
        17:       result[i] *= result[i];
        18:    }
        19:
        20:    #pragma omp parallel for
        21:    for (int i = 0; i < NUM_ELEMENTS; i++) {
        22:       result[i] += 10;
        23:    }
        24: }

Figure 5. Parallel Regions Enclosing Multiple Parallel Loops pattern in an
example from the PCB v1.0. The parallel region reduces the Fork/join overhead
caused by parallelizing each loop individually.

##### Avoiding Load Imbalance Through Dynamic Scheduling

Load imbalance occurs when the computational workload is unevenly distributed
among the available processing units. Load imbalance is a significant source
of performance degradation and limited scalability in parallel computing.
Dynamic scheduling in OpenMP can mitigate this effect by assigning
computational tasks to processing units at runtime based on their load and
availability. Figure 6 illustrates this situation by showcasing a triangular
loop. The default OpenMP scheduler (static) will divide the iterations of the
parallel loop evenly, causing load imbalance.

        1: #pragma omp parallel for schedule(dynamic, 1)
        2: //Every thread will process one iteration of the loop,
        3: // and it will be used as it is available
        4:  for (int i = 0; i < N; i++) {
        5:    for (int j = 0; j < N - i; j++) {
        6:      // With static scheduling: Thread1->N-i,
        7:        // Thread2->N-i-1...
        8:      // ThreadN->1
        9:       array[i][j] = i + j;
       10:    }
       11:  }

Figure 6. Avoiding Load Imbalance Through Dynamic Scheduling pattern in an
example from the PCB v1.0. Inserting the OpenMP clause for dynamic scheduling
resolves the load imbalance.

##### Parallelizing Array Reductions

Array reductions perform operations, such as sum, product, min, or max, on
elements of an array. Parallelizing these operations requires careful
consideration of data dependencies and synchronization to ensure correct
results while maximizing parallel execution. Algorithms to perform reductions
in parallel are well known (Pottenger and Eigenmann, 1995) but applying them
correctly and beneficially when the result is an array itself can be non
trivial (Prema et al., 2017). Figure 7 illustrates this situation.

        1:  #pragma omp parallel for reduction(+:result)
        2:  for (i = 0; i < ARRAY_SIZE; i++) {
        3:       for (j = 0; j < INNER_SIZE; j++) {
        5:          result[j] += array[i][j];
        6:       }
        7:    }
        8:

Figure 7. Parallelizing Array Reduction pattern in an example from the PCB
v1.0. Most compilers can recognize scalar reductions. The analysis is more
difficult, if the reduction variable is an array, as result[] in this example.

##### NOWAIT – Eliminating Barrier Synchronizations

Barriers are essential for maintaining correctness and synchronization in
parallel programs but introduce overhead when some threads complete their work
before others. NOWAIT constructs can be used to eliminate barrier
synchronizations and improve parallel performance by allowing threads to
continue executing. AOTs need to determine the situations where doing so is
legal. Figure 8 illustrates this pattern.

        1: #pragma omp parallel
        2: {
        3:    double local_sum = 0.0;
        4:    for (int i = 0; i < ARRAY_SIZE; i++) {
        5:        for (int j = 0; j < INNER_SIZE; j++) {
        6:             for (int k = 0; k < INNER_SIZE; k++) {
        7:                result[i][j][k]+=matrix_A[i][j][k]
        8:               * matrix_B[i][j][k];
        9:              }
        10:        }
        11:   }
        12:       #pragma omp for nowait
        13:       for (i = 0; i < ARRAY_SIZE; i++) {
        14:         for (j = 0; j < INNER_SIZE; j++) {
        15:             for (k = 0; k < INNER_SIZE; k++) {
        16:                 local_sum += array[i][j][k];
        17:             }
        18:         }
        19:     }
        20:    #pragma omp atomic
        21:     sum += local_sum;
        22:   }

Figure 8. Eliminating Barrier Synchronizations pattern in an example from the
PCB v1.0. An OpenMP NOWAIT clause is inserted to eliminate the barrier
synchronization and improve parallel performance.

##  4\. Evaluation: LLMs versus Classical Optimizing Compilers

This section assesses the current capabilities of two Large Language Models,
GPT-4.0 and CodeLlama-70B, in comparison with three different automatic
compilers, CETUS, PLUTO and ROSE. Section 4.1 outlines the experimental setup,
Section 4.2 evaluates the ability of the LLMs to process and correctly
optimize large code sizes. Section 4.3 examines the ability of these LLMs to
optimize code sections effectively and also assesses their capacity in
handling the challenge patterns introduced in Section 3.2. Lastly, Section 4.4
compares the achieved speedup of all five Automatic Optimization Tools (AOTs).

###  4.1. Experimental setup

To assess our Automatic Optimization Tools, we use the PCAOT environment
described in Section 3.1. Our test suite drew from three distinct benchmarks:
The NPB v3.3 (Bailey et al., 1991) , the PB suite V4.2 (Yuki and Pouchet, [n.
d.]), and the PCB benchmark introduced in Section 3.2. For our experiments, we
measured the performance of the applications using input Class B for the NPB
and the LARGE_DATASET for the PB and PCB suite.

We have selected specific subroutines from the NPB and the PB suites that
represent challenge patterns. For the PCB, we developed 20 use cases, with
each one representing one of the six challenge scenarios detailed in Section
3.2.

Table 1 displays our test suite. We set the following AOT parameters: For the
CETUS, PLUTO and ROSE compilers we chose their default options, selecting the
known, safe optimization behavior. For the LLMs, we chose a Temperature of 0.2
and a Top_p value of 0.1, increasing deterministic behavior for the code
generation tasks.

Table 1. Testing Dataset: Experimental Section, Impact of the experimental section on the overall application, Pattern evaluated, and number of loops we are testing with the AOTs Benchmark | Application Name | Experimental Section | Impact % | Pattern evaluated | #Loops
---|---|---|---|---|---
NAS | BT | initialize | 0.2% | PF, PR | 11
NAS | BT | rhs_norm | 0.5% | PR, PO, NW | 1
NAS | BT | compute_rhs | 10.2% | PR, PO | 11
NAS | BT | x_solve | 27.7% | PF, PO | 1
NAS | SP | initialize | 0.3% | PF, PR | 11
NAS | SP | rhs_norm | 0.2% | PF, PR | 1
NAS | SP | y_solve | 19.6% | PF, PO | 1
NAS | SP | exact_rhs | 0.3% | PR, PO, NW | 5
NAS | MG | norm2u3 | 1.1% | PF, PR, NW | 1
NAS | MG | zran3 | 29.3% | PF, PR | 3
NAS | CG | conj_grad | 98.9% | PR, PA, PO, NW | 5
NAS | IS | full_verify | 99.8% | DS, PO | 5
Poly | Linear Algebra | 2mm | 91.8% | PR, PO | 1
Poly | Linear Algebra | 3mm | 98.4% | PR, PO | 3
Poly | Linear Algebra | Atax | 18.2% | PR, PO | 5
Poly | Datamining | Correlation | 99% | PR, PO | 1
PCB | Challenges | PO_Function_Version[1-5] | 97% | PO | 5
PCB | Challenges | PF_Function_Version[1-3] | 93% | PF | 4
PCB | Challenges | PR_Function_Version[1-3] | 98% | PR | 9
PCB | Challenges | DS_Function_Version[1-3] | 96.3% | DS | 3
PCB | Challenges | PA_Function_Version[1-3] | 95% | PA | 4
PCB | Challenges | NW_Function_Version[1-3] | 97.2% | NW | 3

We measured execution times on a compute node featuring a 4-core Intel Xeon
Gold 6230 processor configuration in dual sockets. Each processor operates at
a base frequency of 2.1 GHz, with a 27.5MB cache, and was supported by up to 1
GB of DDR4 memory. Application codes were compiled using GCC v4.8.5 with -O3
optimization on CentOS v7.4.1708. Reported values represent the median of
three application runs, each utilizing one thread per core.

###  4.2. Impact of Code Size

Table 2, shows the capacity of the Large Language Models to process programs
with large code sizes. This table displays the number of lines of code per
experimental section versus the successful cases after sending the two
different prompts described in Section 3.1.1, 3 times each to the two chosen
LLMs; GTP4.0 and Codellama-70B, with a total of 192 attempts.

These results illustrate the capability of the LLMs in handling large code
sizes. While smaller code sections tend to be transformed more accurately,
they are not guaranteed to be 100% correct. As the code size increases, the
likelihood of inaccuracies also increases.

Program sections of approximately 20 lines often produce correct output,
whereas no section above 200 lines was transformed successfully (performance
will be evaluated later). In between, the LLMs exhibit non-deterministic
behavior, with some runs producing useful results while others with the same
input fail. GPT4.0 and Codellama-70B return successfully transformed code in
14.06% of the cases.

These results further justify our method of employing LLM capabilities on the
basis of individual program sections.

###  4.3. LLM Optimization Capabilities

Figure 9 shows the success rates of generating correctly optimized code by the
tested LLMs on specific challenge patterns, using the two prompts described in
Section 3.1.1. The results are classified into four distinct categories:
Pattern correctly applied, Pattern not correctly applied but code compiles,
Compilation error, Incorrect Result and Runtime error.

Table 2. Capacity of Large Language Models to process large programs Large
Language Model
---
GPT4.0 | CodeLlama-70B
Benchmark |  | Experimental
---
Section
| #Lines
---
code
| Succesfull
---
Cases
Benchmark |  | Experimental
---
Section
| #Lines
---
code
| Sucessfull
---
cases
| BT
---
Linear Algebra
Datamining
SP
MG
Linear Algebra
Linear Algebra
IS
BT
SP
CG
MG
SP
SP
BT
BT
| rhs_norm
---
Atax
Correlation
rhs_norm
norm2u3
2mm
3mm
full_verify
Initialize
Initialize
conj_grand
zran3
y_solve
exact_rhs
x_solve
compute_rhs
| 18
---
21
21
26
28
29
34
41
155
161
183
187
250
313
346
382
| 3
---
5
5
0
2
6
6
0
0
0
0
0
0
0
0
0
| BT
---
Linear Algebra
Datamining
SP
MG
Linear Algebra
Linear Algebra
IS
BT
SP
CG
MG
SP
SP
BT
BT
| rhs_norm
---
Atax
Correlation
rhs_norm
norm2u3
2mm
3mm
full_verify
Initialize
Initialize
conj_grand
zran3
y_solve
exact_rhs
x_solve
compute_rhs
| 18
---
21
21
26
28
29
34
41
155
161
183
187
250
313
346
382
| 2
---
5
5
0
0
6
6
0
0
0
3
0
0
0
0
0
Figure 9. Correctness Evaluation for the following challenging patterns: Array
Reduction, NOWAIT, Parallel-Regions, Parallelization at the Outermost level
(P-Outermost), Parallelization for function calls (P-Function Calls), Dynamic
Scheduling (Dynamic Sch)
GPT4-CoTGPT4-IPCLLama-70B-CoTCLLama-70B-IPGPT4-COTGPT4-IPCLLama-70B-CoTCLLama-70B-IPGPT4-CoTGPT4-IPCLLama-70B-CoTCLLama-70-IPGPT4-CoTGPT4-IPCLLama-70B-CoTCLLama-70-IPGPT4-CoTGPT4-IPCLLama-70B-CoTCLLama-70B-IPGPT4-CoTGPT4-IPCLLama-70B-CoTCLLama-70B-IP$0$$20$$40$$60$$80$$100$$25$%
$41.7$% $41.7$% $15.2$% $31.8$% $28.8$% $21.7$% $20.2$% $25$% $25$% $15.2$%
$21.2$% $18.6$% $20.9$% $31.8$% $20.2$% $18.7$% $17.3$% $25$% $72.7$% $71.2$%
$47$% $59.1$% $63.6$% $64.3$% $44.2$% $57.4$% $33.3$% $75$% $33.3$% $75$%
Array ReductionNOWAITParallel-RegionsP-OutermostP-Fuction CallsDynamic
SchPercentagePattern Correctly Applied (%)Pattern No Correctly Applied but
Compiled(%)Compilation Error (%)Incorrect Code(%)Runtime Error (%)

Our primary finding from this information is that LLMs are not yet in a
position where they can serve as automatic optimizers. Only in three of the
analyzed optimization patterns, both LLMs produce partly incorrect results. A
key demand on automatic optimizers is that they be 100% correct; tools that
require software engineers to engage in possibly lengthy debug phases after
use are not acceptable. The partial successes in two of the patterns (Array
Reduction and Parallelizing Outermost Loop) indicate that LLMs may be making
progress toward the goal of becoming useful AOTs. These two patterns represent
some of the most important parallelization capabilities and likely have many
code examples serving as LLM training data, which may explain the partial
success. The NOWAIT and Parallel-Region patterns tend to involve large code
regions, which challenge LLMs, as discussed in Section 4.2. The two LLMs
completely fail on Dynamic Scheduling patterns. We attribute this behavior to
the more complex code exhibited by such test cases. Dynamic scheduling tends
to be needed in loops that involve irregular code and data structures, which
are more difficult to comprehend.

The results show no significant difference between the two prompting methods
we used. While other researchers have reported more success with Chain-of-
Thought (CoT) prompting, this method performed marginally worse in some cases
than the more direct Instruction Prompting (IP) method. Finally, comparing the
two LLMs shows insignificant differences as well. CodeLLama is optimized for
program code synthesis, as well as infilling/completion (Grattafiori et al.,
2023), hence we expected it to perform well. However, ChatGPT has a larger
number of AI model parameters, which may make up for the fact that it is a
general model.

###  4.4. Speedup Evaluation

Figure 10 shows the maximum average speedups for correct and incorrect code
obtained from the five distinct AOTs across our three benchmark suites against
each benchmark’s baseline (Serial code) and its Hand-optimized version.

Figure 10. AOTs - Speedup Evaluation of each AOT using a specific
configuration: Chain-of-Thought and Instruction prompting for LLMs and the
default configuration for the optimizing
compilers.GPT4-CoTGPT4-IPCLLama-70B-CoTCLLama-70B-IPCETUSROSEHANDGPT4-CoTGPT4-IPCLLama-70B-CoTCLLama-70B-IPCETUSPLUTOROSEGPT4-CoTGPT4-IPCLLama-70B-CoTCLLama-70B-IPCETUSROSEHAND$0$$2$$4$$6$$8$x$1.1$
x$1.1$ x$0.8$ x$1.3$ x$1.6$ x$1.9$ x$1$ x$2.3$ x$1.6$ x$2$ x$2.1$ x$2$ x$1.6$
x$7$ x$1.3$ x$1.4$ x$1.2$ x$1.9$ x$1.6$ x$1.5$ x$1.2$ x$2.2$
NASPolyBenchPCBSpeed upAverage speedUpAdditional speedUp but Incorrect Code

Our findings demonstrate the efficacy of CodeLlama-70B as the superior
optimizer among Language Model-based (LLM) solutions, capable of achieving
speedups of up to 2.1x compared to the original program, measuring correct
code only. When considering incorrectly optimized code as well, the achieved
speedup is approximately 2.7x.

Conversely, we can observe a noticeable difference between all the AOTs and
PLUTO in terms of speedup achieved within the PolyBenchmark suite, where PLUTO
outperformed all of the AOTs with a remarkable 7x speedup. This superior
performance is attributed to PLUTO’s specialization on the Polyhedral model
(Bondhugula et al., 2008b). The specialization may also explain why PLUTO was
unable to process the other benchmark suites.

Overall, CETUS emerged as the best among the optimizing compilers for
processing a variety of programs within these suites, achieving a maximum
speedup of 1.9x. The ROSE optimizer achieved a speedup across all benchmarks
of 1.2x, remaining below the other AOTs in terms of efficacy.

While GPT4 has demonstrated success across various tasks, it exhibited the
lowest performance for code optimization across all the benchmarks and among
the LLMs. It achieved a maximum speedup of 1.6x, falling short of
CodeLlama-70B.

##  5\. Related work

The primary objective of PCAOT is to automatically validate the correctness
and performance of optimizations generated by Automatic Optimization Tools
(AOTs). To the best of our knowledge, no other research has directly addressed
this specific objective. However, several studies have created benchmarks to
evaluate the capabilities of Large Language Models (LLMs) in optimization
tasks.

For instance, HumanEval (Black et al., 2022) is a benchmark designed to assess
the performance of LLMs in generating correct and efficient code.
Additionally, there has been a study evaluating the ability of LLMs to
synthesize short programs from natural language descriptions, demonstrating
the potential of these models in code generation tasks (Austin et al., 2021).

Recent studies have also evaluated the performance of LLMs in specific High-
Performance Computing (HPC) optimization tasks; such as OpenMP pragma
prediction (Nichols et al., 2023) highlighting the application of LLMs in
parallel computing optimizations. Additionally, approaches to code completion
(Valero-Lara et al., 2023) and issue fixing (Valero-Lara et al., 2023) show
the breadth of LLM applications in software development and maintenance.

Another significant contribution in this domain is the novel paradigm
introduced by researchers using Large Language Models with compiler feedback
to optimize the code size of LLVM assembly. Their model takes unoptimized LLVM
Intermediate Representation (IR) as input and produces optimized IR,
optimization passes, and instruction counts for both unoptimized and optimized
IRs (Grubisic et al., 2024).

Despite these advancements, the automatic validation of both the correctness
and performance of optimizations remains underexplored. Our work aims to fill
this gap by providing a comprehensive framework for evaluating and validating
the outputs of AOTs, ensuring that the generated optimizations meet the
desired standards of correctness. We also proposed a novel Parallel Computing
Challenge Benchmark suite (PCB) V1.0 containing six challenge patterns for
evaluating AOT code optimization capabilities.

##  6\. Conclusions

This paper introduced a novel mechanism called PCAOT, which enables the
automatic validation of the correctness and performance of Automatic
Optimization Tools-generated code. While we have applied the mechanism to
verify LLM-generated code, it also enables unsafe compiler optimization to be
tested. Additionally, we have presented the Parallel Computing Challenge
Benchmark suite (PCB) v1.0, comprising 20 use cases for evaluating the
capabilities of Automatic Optimization Tools. To the best of our knowledge,
this is the first such benchmark.

Our results show that LLMs only succeed in optimizing very small programs of
approximately 20 lines. Given that real-world software often contains
thousands of lines of code, these models are not yet ready to serve as
automatic optimizers.

Our results also show that LLMs perform only marginally better than current
optimizing compilers, in terms of correctness. The chosen LLMs can correctly
identify three out of the six different challenge patterns, such as Array
Reduction, Parallelizing Outermost Loops, and Loops Containing Function Calls,
with a success rate higher than 50% in most cases. However, they often fail on
other patterns, including eliminating barrier synchronization using the NOWAIT
clause, parallel regions enclosing multiple parallel loops, and avoiding load
imbalance through dynamic scheduling.

In terms of speedup, the best compiler and the best LLM performed within 10%.
We also found no significant difference between the two prompting methods we
employed, with Chain-of-Thought (CoT) performing slightly worse in some cases
than the more straightforward Instruction Prompting (IP) method.

Finally, addressing the main question asked in the introduction:  Can AI-
driven models revolutionize the way we approach code optimization? We find
that, with their current capabilities, the LLMs cannot yet suitably serve as
Automatic Optimization Tools. Even though the potential exists, future LLMs
will need significant improvements in terms of performance and correctness.

.

##  7\. ACKNOWLEDGEMENTS

This work was supported in part by the University of Delaware and by the
National Science Foundation under awards 2112606, 2125703, and 1931339.

## References

  * (1)
  * Achiam et al. (2023) Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023\.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_ (2023).
  * Asher et al. (2023) Nicholas Asher, Swarnadeep Bhar, Akshay Chaturvedi, Julie Hunter, and Soumya Paul. 2023.  Limits for learning with language models.  _arXiv preprint arXiv:2306.12213_ (2023).
  * Austin et al. (2021) Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. 2021\.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_ (2021).
  * Bae et al. (2013) Hansang Bae, Dheya Mustafa, Jae-Woo Lee, Aurangzeb, Hao Lin, Chirag Dave, Rudolf Eigenmann, and Samuel P Midkiff. 2013.  The cetus source-to-source compiler infrastructure: overview and evaluation.  _International Journal of Parallel Programming_ 41 (2013), 753–767.
  * Bailey et al. (1991) David H Bailey, Eric Barszcz, John T Barton, David S Browning, Robert L Carter, Leonardo Dagum, Rod A Fatoohi, Paul O Frederickson, Thomas A Lasinski, Rob S Schreiber, et al. 1991\.  The NAS parallel benchmarks—summary and preliminary results. In _Proceedings of the 1991 ACM/IEEE Conference on Supercomputing_. 158–165.
  * Barakhshan and Eigenmann (2023a) Parinaz Barakhshan and Rudolf Eigenmann. 2023a.  CaRV–Accelerating Program Optimization through Capture, Replay, Validate. In _Proceedings of the SC’23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis_. 654–662.
  * Barakhshan and Eigenmann (2023b) Parinaz Barakhshan and Rudolf Eigenmann. 2023b.  Learning from Automatically Versus Manually Parallelized NAS Benchmarks. In _International Workshop on Languages and Compilers for Parallel Computing_. Springer, 29–46.  https://link.springer.com/chapter/10.1007/978-3-031-31445-2_3.
  * Bhosale et al. (2022) Akshay Bhosale, Parinaz Barakhshan, Miguel Romero Rosas, and Rudolf Eigenmann. 2022.  Automatic and interactive program parallelization using the Cetus source to source compiler infrastructure v2. 0.  _Electronics_ 11, 5 (2022), 809.
  * Black et al. (2022) Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, et al. 2022\.  Gpt-neox-20b: An open-source autoregressive language model.  _arXiv preprint arXiv:2204.06745_ (2022).
  * Bondhugula et al. (2008a) Uday Bondhugula, Muthu Baskaran, Sriram Krishnamoorthy, J. Ramanujam, A. Rountev, and P. Sadayappan. 2008a.  Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model. In _International Conference on Compiler Construction (ETAPS CC)_.
  * Bondhugula et al. (2008b) Uday Bondhugula, Muthu Baskaran, Sriram Krishnamoorthy, J. Ramanujam, Atanas Rountev, and P. Sadayappan. 2008b.  Automatic Transformations for Communication-Minimized Parallelization and Locality Optimization in the Polyhedral Model. In _Compiler Construction_ , Laurie Hendren (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 132–146.
  * Chen et al. (2023) Le Chen, Pei-Hung Lin, Tristan Vanderbruggen, Chunhua Liao, Murali Emani, and Bronis de Supinski. 2023.  Lm4hpc: Towards effective language model application in high-performance computing. In _International Workshop on OpenMP_. Springer, 18–33.
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021\.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ (2021).
  * Grattafiori et al. (2023) Wenhan Xiong Grattafiori, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. 2023.  Code Llama: Open Foundation Models for Code.  _arXiv preprint arXiv:2308.12950_ (2023).
  * Grubisic et al. (2024) Dejan Grubisic, Chris Cummins, Volker Seeker, and Hugh Leather. 2024.  Compiler generated feedback for Large Language Models.  _arXiv preprint arXiv:2403.14714_ (2024).
  * Gupta et al. (2022) Prakhar Gupta, Cathy Jiao, Yi-Ting Yeh, Shikib Mehri, Maxine Eskenazi, and Jeffrey P Bigham. 2022.  InstructDial: Improving zero and few-shot generalization in dialogue through instruction tuning.  _arXiv preprint arXiv:2205.12673_ (2022).
  * Kadosh et al. (2023) Tal Kadosh, Nadav Schneider, Niranjan Hasabnis, Timothy Mattson, Yuval Pinter, and Gal Oren. 2023.  Advising openmp parallelization via a graph-based approach with transformers. In _International Workshop on OpenMP_. Springer, 3–17.
  * Leiserson et al. (2020) Charles E. Leiserson, Neil C. Thompson, Joel S. Emer, Bradley C. Kuszmaul, Butler W. Lampson, Daniel Sanchez, and Tao B. Schardl. 2020.  There’s plenty of room at the Top: What will drive computer performance after Moore’s law?  _Science_ 368, 6495 (2020), eaam9744.  https://doi.org/10.1126/science.aam9744 arXiv:https://www.science.org/doi/pdf/10.1126/science.aam9744
  * Li et al. (2014) Fengqian Li, Feilong Tang, and Yao Shen. 2014.  Feature mining for machine learning based compilation optimization. In _2014 Eighth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing_. IEEE, 207–214.
  * Li et al. (2023) Raymond Li, Loubna Ben Allal, Yangtian Zi, Niklas Muennighoff, Denis Kocetkov, Chenghao Mou, Marc Marone, Christopher Akiki, Jia Li, Jenny Chim, et al. 2023\.  Starcoder: may the source be with you!  _arXiv preprint arXiv:2305.06161_ (2023).
  * Li et al. (2022) Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al. 2022\.  Competition-level code generation with alphacode.  _Science_ 378, 6624 (2022), 1092–1097.
  * Liu et al. (2023) Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. 2023.  Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation.  arXiv:2305.01210 [cs.SE]
  * META ([n. d.]) META. [n. d.].  _CodeLlama B-70_.  https://huggingface.co/chat/
  * META ([n. d.]) META. [n. d.].  _CodeLlama B-70 tokens_.  https://huggingface.co/codellama/CodeLlama-70b-Instruct-hf
  * Mishra et al. (2021) Swaroop Mishra, Daniel Khashabi, Chitta Baral, Yejin Choi, and Hannaneh Hajishirzi. 2021.  Reframing Instructional Prompts to GPTk’s Language.  _arXiv preprint arXiv:2109.07830_ (2021).
  * Monsifrot et al. (2002) Antoine Monsifrot, François Bodin, and Rene Quiniou. 2002.  A machine learning approach to automatic production of compiler heuristics. In _Artificial Intelligence: Methodology, Systems, and Applications: 10th International Conference, AIMSA 2002 Varna, Bulgaria, September 4–6, 2002 Proceedings 10_. Springer, 41–50.
  * Nichols et al. (2023) Daniel Nichols, Aniruddha Marathe, Harshitha Menon, Todd Gamblin, and Abhinav Bhatele. 2023.  Modeling parallel programs using large language models.  _arXiv preprint arXiv:2306.17281_ (2023).
  * OpenAI ([n. d.]) OpenAI. [n. d.].  _ChatGPT_.  https://chat.openai.com/
  * OpenAI ([n. d.]) OpenAI. [n. d.].  _GPT4_.  https://platform.openai.com/docs/models/gpt-4-turbo-and-gpt-4
  * Pornmaneerattanatri et al. (2024) Soratouch Pornmaneerattanatri, Keichi Takahashi, Yutaro Kashiwa, Kohei Ichikawa, and Hajimu Iida. 2024.  Parallelizable Loop Detection using Pre-trained Transformer Models for Code Understanding. In _Parallel and Distributed Computing, Applications and Technologies_ , Ji Su Park, Hiroyuki Takizawa, Hong Shen, and James J. Park (Eds.). Springer Nature Singapore, Singapore, 32–42.
  * Pottenger and Eigenmann (1995) Bill Pottenger and Rudolf Eigenmann. 1995.  Idiom Recognition in the Polaris Parallelizing Compiler. In _The 9th ACM International Conference on Supercomputing (ICS’95)_. ACM Press, 444–448.  https://doi.org/10.1145/224538.224655
  * Prema et al. (2017) S Prema, R Jehadeesan, and BK Panigrahi. 2017.  Identifying pitfalls in automatic parallelization of NAS parallel benchmarks. In _2017 National Conference on Parallel Computing Technologies (PARCOMPTECH)_. IEEE, 1–6.
  * Quinlan and Liao (2011) Dan Quinlan and Chunhua Liao. 2011.  The ROSE source-to-source compiler infrastructure. In _Cetus users and compiler infrastructure workshop, in conjunction with PACT_ , Vol. 2011. Citeseer, 1.
  * Shypula et al. (2023) Alexander Shypula, Aman Madaan, Yimeng Zeng, Uri Alon, Jacob Gardner, Milad Hashemi, Graham Neubig, Parthasarathy Ranganathan, Osbert Bastani, and Amir Yazdanbakhsh. 2023.  Learning performance-improving code edits.  _arXiv preprint arXiv:2302.07867_ (2023).
  * Valero-Lara et al. (2023) Pedro Valero-Lara, Alexis Huante, Mustafa Al Lail, William F Godoy, Keita Teranishi, Prasanna Balaprakash, and Jeffrey S Vetter. 2023.  Comparing Llama-2 and GPT-3 LLMs for HPC kernels generation.  _arXiv preprint arXiv:2309.07103_ (2023).
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022.  Chain-of-Thought Prompting Elicits Reasoning in Large Language Models. In _Advances in Neural Information Processing Systems_ , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (Eds.), Vol. 35. Curran Associates, Inc., 24824–24837.  https://proceedings.neurips.cc/paper_files/paper/2022/file/9d5609613524ecf4f15af0f7b31abca4-Paper-Conference.pdf
  * Yuki and Pouchet ([n. d.]) T. Yuki and L.N. Pouchet. [n. d.].  _PolyBenchC-4.2.1_.  Accessed on 2021-01-05.
  * Zhao et al. (2005) Min Zhao, Bruce R Childers, and Mary Lou Soffa. 2005.  A model-based framework: an approach for profit-driven optimization. In _International Symposium on Code Generation and Optimization_. IEEE, 317–327.


# Pseudo-random generators using linear feedback shift registers with output
extraction

Holger Nobach
Max Planck Institute for Dynamics and Self-Organization
Am Faßberg 17, 37077 Göttingen, Germany
<EMAIL_ADDRESS>
###### Abstract

The use of three extractors, fed by linear feedback shift registers (LFSR) for
generating pseudo-random bit streams is investigated. Specifically, a standard
LFSR is combined with a von Neumann extractor, a modified LFSR, extended by
the all-zero state, is combined with an output logic, which translates every
three bits from the LFSR into up to two output bits and a run extraction of
the input bit stream into single output bits are investigated. The latter two
achieve better efficiency in using bits from the primary bit stream, the last
one reaches 50%. Compared to other generator logics, the three extractors
investigated are less performant in terms of their cryptographic strength.
However, the focus of this report is on the quality of the pseudo-random bit
stream in comparison to really random bits and on the efficiency of using the
bits of the primary stream from the LFSR and generating valid output bits,
while fulfilling a minimum cryptographic strength only, beyond that of the
pure LFSR.

##  1 Introduction

Linear feedback shift registers (LFSR) are a broad class of pseudo-random bit
stream generators, which are widely used because of their simplicity and their
good signal characteristics in terms of periodicity with long periods,
correlation, run lengths and balance of zeros and ones. Unfortunately, they
are cryptographically weak — for an $n$-bit long shift register a sequence of
$2n$ stream bits is sufficient to construct at least an adequate linear
feedback circuit and the appropriate initial state of the register, which can
reproduce the complete bit sequence [1].

To improve the cryptographic strength of a pseudo-random stream generator
based on LFSRs, three basic concepts are generally used: (non-linear) output
filters, (non-linear) combinations of multiple LFSRs or clock controlled
LFSRs. Generators based on non-linear feedback shift registers are the
ultimate solution, however, this is beyond the present discussion. Non-linear
output filters and non-linear combinations of LFSRs often lead to biased bit
streams with unequal distributions of zeros and ones. To obtain an unbiased
output bit stream from a biased input, the von Neumann extractor [2] can be
used, which translates the four possible combinations of two consecutive input
bits into three possible states of the output one, zero or invalid/discarded,
where the valid output bits are obtained from combinations with identical
probabilities, finally leading to an unbiased output sequence.

Alternatively, a self-shrinking generator [3] also introduces cryptographic
strength to an unbiased but weak bit sequence from an LFSR. The self-shrinking
logic can be interpreted as a certain form of a clock controlled LFSR, where
some bits from the primary stream are discarded by pulsing the LFSR multiple
times between the bits selected and given out. The von Neumann extractor and
the self-shrinking generator, both read two consecutive bits from the primary
bit stream at once and generate either one valid output bit, zero or one, or
no valid output bit. The difference between these two extraction logics is the
mapping of the four input combinations to the output states. However, the von
Neumann extractor seems a probable alternative to the self-shrinking logic to
obtain cryptographic strength, even if the feature of the von Neumann
extractor to correct a biased bit stream is not needed in combination with
LFSRs.

Since the von Neumann extractor generates one output bit from two input bits,
and this on average in half of the bit combinations, while the other half of
the bit combinations gets discarded, the efficiency of such a generator in
generated bits per primary input bit is approximately $\nicefrac{{1}}{{4}}$.
Options to increase the efficiency of generating output bits from input bits
and lowering the number of discarded bits are to increase the size of input
chunks and generate more than one bit out of them [4] or to reuse discarded
bits from the input stream [5] to produce more output bits from a given input
sequence.

In this report, an LFSR was first combined with a von Neumann extractor. Some
basic statistical investigations are given. The ideas to increase the chunk
size and to produce multiple bits and that to reuse bits from the input stream
are also being pursued, however in a different way than in the publications
above. Since the input stream coming from the LFSR is already unbiased, the
extractors do not have to worry about eliminating any bias. So the focus of
the extraction logic defined by the mapping of input onto output bit
combinations can be on the quality of the generated bit stream compared to
that of real random noise at a minimum cryptographic strength, at least above
that of the pure LFSR. Particularly, an extraction scheme is proposed,
generating up to two output bits from every three input bits coming from the
feeding LFSR and reaching an efficiency of $\nicefrac{{5}}{{12}}$.
Furthermore, an extractor is investigated, deriving one valid bit or an
invalid one like the von Neumann extractor from three input bits, however, the
LFSR is pulsed only once, reading one new bit from the LFSR and recycling the
previous two bits, reaching an efficiency of $\nicefrac{{1}}{{2}}$.

All these logics derive their cryptographic strength from the fact that the
output stream withholds information on how many bits of the primary stream
have been discarded or have not been used in between two consecutive bits of
the output stream and which values they have had. On the other side, this
means that the more efficient the logic uses the input bits, the weaker the
entire generator is. However, the focus of the present investigation is more
on the efficiency of the generators having at least some cryptographic
strength beyond the pure LFSR. For high cryptographic demands, other
generators will be better suited [6, 7].

Note that the term “extractor” is appropriate for the von Neumann and for the
run extractors only, since they extract bits from the primary LFSR stream and
discards others. The three-bit logic uses a translation table instead, which
does not correspond directly with the bits from the primary stream. However,
for readability reason, the term “extractor” is generally used for all three
logics.

The Python programs used for this test with the three generator logics are
openly available at http://www.nambis.de/publications/arxiv24a.html.

##  2 Standard Linear Feedback Shift Register

$\overline{\hbox{Q}}$ D Q 1$\overline{\hbox{Q}}$ D Q 2$\overline{\hbox{Q}}$ D
Q 3…$\overline{\hbox{Q}}$ D Q 11$\overline{\hbox{Q}}$ D Q
12$\overline{\hbox{Q}}$ D Q 13$\overline{\hbox{Q}}$ D Q
14$\overline{\hbox{Q}}$ D Q 15$\overline{\hbox{Q}}$ D Q 16$a_{i}$CLK Figure 1:
Standard Fibonacci-type 16-bit LFSR with a period of $2^{16}-1$ internal
states

For the present investigation a 16-bit standard Fibonacci-type LFSR (sLFSR16,
Fig. 1) is used to generate the primary bit stream $a_{i}$. A primitive
polynomial for this LFSR [8] gives a possible structure to obtain the maximum
cycle length of $2^{16}-1$ states by feeding back certain bits of the register
to its input using three XOR gates. For practical applications the length $n$
of the LFSR should be larger, yielding $2^{n}-1$ steps long periods of the
primary bit stream and finally long periods of the output bit stream after the
following extraction. So far, 160-bit LFSRs seem to be a good choice, where
the initialization of the LFSR can be done with an SHA-1 hash obtained from a
secret password.

##  3 Von Neumann extractor

sLFSR$a_{i}$von Neumann extractortranslation
table$a_{2j},a_{2j+1}\Longrightarrow b_{j}$three-state($0$, $1$ and
$\Lambda$)$b_{j}$valid states($0$ and $1$) Figure 2: Pseudo-random generator
using a standard LFSR in combination with a von Neumann extractor

To break the vulnerability of LFSRs to their predictability, shrinking the bit
stream by selecting parts of the bits from the primary stream and discarding
the others has been found to be an appropriate means. The von Neumann
extractor originally selects individual bits from a biased input bit stream to
obtain an unbiased output. However, this extractor is also useful to introduce
some cryptographic strength to a bit stream obtained from an LFSR (Fig. 2).
The translation table of the von Neumann extractor (Tab. 1) assigns the three
possible output states zero ($0$), one ($1$) and invalid ($\Lambda$) of the
output bit $b_{j}$ to the two consecutive primary input bits $a_{2j}$ and
$a_{2j+1}$.

Note that the shift register is pulsed twice for reading the two primary bits
into the von Neumann extractor at once to either generate one valid output bit
or an invalid one. In any case, both primary input bits were consumed. If the
von Neumann extractor is recycling one bit of the input stream for the next
output by shifting the bits of the LFSR only once per extractor output step,
the output sequence will end in a regular pattern of alternating zeros and
ones. Therefore, the von Neumann extractor always reads two bits from the LFSR
at once and one full period of the shrunken output stream is reached after two
full periods of the primary stream, because a standard LFSR has a period of
the generated primary bit stream, which is not divisible by two.

Table 1: Translation table of the von Neumann extractor input bits $a_{2j}$ and $a_{2j+1}$ | output bit $b_{j}$
---|---
$\begin{array}[]{cc}0&0\\\ 0&1\\\ 1&0\\\ 1&1\end{array}$ |  $\begin{array}[]{c}\Lambda\\\ 1\\\ 0\\\ {}\Lambda\end{array}$

##  4 Extended Linear Feedback Shift Register

$\overline{\hbox{Q}}$ D Q 1$\overline{\hbox{Q}}$ D Q 2$\overline{\hbox{Q}}$ D
Q 3…$\overline{\hbox{Q}}$ D Q 11$\overline{\hbox{Q}}$ D Q
12$\overline{\hbox{Q}}$ D Q 13$\overline{\hbox{Q}}$ D Q
14$\overline{\hbox{Q}}$ D Q 15$\overline{\hbox{Q}}$ D Q 16$a_{i}$CLK…… Figure
3: Extended Fibonacci-type 16-bit LFSR with a period of $2^{16}$ internal
states

To obtain long periods of the output stream, the cycle length of the LFSR
should be chosen to be coprime with the number of input bits read by the
following extractor. The von Neumann extractor reads two consecutive bits from
the primary bit stream, and the cycle length of standard LFSRs of $2^{n}-1$ is
coprime for any register length $n$.

In combination with the following three-bit extractor, this coprime
requirement is not met for all lengths $n$ of standard LFSRs. To achieve
maximum flexibility in choosing the length of the LFSR, the feedback input of
the LFSR is slightly modified (Fig. 3). By adding one extra XOR gate and a
NAND gate with $n-1$ inputs, the period of the LFSR is extended by the
otherwise missing state of the standard LFSR, where all bits of the register
are zero. The NAND gate together with the additional XOR gate at the input of
the register inverts the input line if the first $n-1$ bits are zero. In this
way, the all-zero state is inserted into the sequence between the last
standard state of the LFSR, with the last flip-flop one and all others zero,
and the first standard state with the first flip-flop one and all others zero.

The obtained period of the bit stream from the extended LFSR (eLFSR) with $n$
registers is then $2^{n}$, which is always coprime with the three bits read by
the following three-bit extractor.

##  5 Three-bit extractor

eLFSR$a_{i}$three-bit extractortranslation table$a_{3j},a_{3j+1},a_{3j+2}\Longrightarrow b_{2j},b_{2j+1}$three-state($0$, $1$ and $\Lambda$)$b_{2j},b_{2j+1}$valid states($0$ and $1$) Figure 4: Pseudo-random generator using an extended LFSR in combination with a three-bit extractor Table 2: Translation table of the three-bit extractor input bits $a_{3j}$, $a_{3j+1}$ and $a_{3j+2}$ | output bits $b_{2j}$ and $b_{2j+1}$
---|---
$\begin{array}[]{ccc}0&0&0\\\ 0&0&1\\\ 0&1&0\\\ 0&1&1\\\ 1&0&0\\\ 1&0&1\\\ 1&1&0\\\ 1&1&1\end{array}$ |  $\begin{array}[]{cc}\Lambda&\Lambda\\\ 0&\Lambda\\\ 1&1\\\ 0&1\\\ 1&0\\\ 1&\Lambda\\\ 0&0\\\ {}\Lambda&\Lambda\end{array}$

In analogy to the von Neumann extractor and using the idea of reading larger
chunks of bit to increase the efficiency of the generator from [4], a new
translation table (Fig. 4 and Tab. 2) has been designed, which uses every
three bits of the primary LFSR bit stream to derive up to two valid output
bits. Two of the eight input combinations give no valid output bit, two others
give one valid output bit and the last four input combinations give the four
combinations with two valid output bits. The translation table does not
consider bias correction, since the input stream from the LFSR is already
unbiased. It is designed to maximize the variance of the output stream with
respect to the variations of the input stream. Because this table is critical
for the effort to break the pseudo-random generator, it could be subject to
updates, if it is later found to be weak.

Since this extractor uses every three consecutive bits of the primary bit
stream from the LFSR, the extended LFSR (eLFSR) is used as input, yielding a
period of the primary bit stream, which is coprime with the three bits read by
the extractor.

##  6 Run extractor

sLFSR$a_{i}$Run extractortranslation table$a_{j},a_{j+1},a_{j+2}\Longrightarrow b_{j}$three-state($0$, $1$ and $\Lambda$)$b_{j}$valid states($0$ and $1$) Figure 5: Pseudo-random generator using a standard LFSR in combination with a run extractor (three-bit interpretation) Table 3: Translation table of the run extractor (three-bit interpretation) input bits $a_{j}$, $a_{j+1}$ and $a_{j+2}$ | output bit $b_{j}$
---|---
$\begin{array}[]{ccc}0&0&0\\\ 0&0&1\\\ 0&1&0\\\ 0&1&1\\\ 1&0&0\\\ 1&0&1\\\ 1&1&0\\\ 1&1&1\end{array}$ |  $\begin{array}[]{c}\Lambda\\\ {}\Lambda\\\ 0\\\ 1\\\ 0\\\ 1\\\ {}\Lambda\\\ {}\Lambda\end{array}$

Since the von Neumann extractor reads two consecutive bits at once from the
primary bit stream of the LFSR, the efficiency of generating output bits out
of the input stream is about $\nicefrac{{1}}{{4}}$ only. A higher efficiency
would be the result, if input bits from the LFSR could be recycled by keeping
one bit from the last reading step and read one new bit from the LFSR only for
the next output. Unfortunately, this results in a permanent sequence of
alternating zeros and ones. This behavior is originated in the fact that the
von Neumann extractor uses the combination of the two consecutive input bits
to derive both, the selection decision and the data bit. The two bits must be
different to generate a valid output bit. This is the case at the end of runs
of either zeros or ones independent of their run lengths. Since the runs of
zeros and ones occur alternately, they are finally shrunken down to an
alternating series of single zeros and ones.

Using two of three consecutive bits from the LFSR to obtain the selection
decision and using a third and separate bit in the bit sequence as the data
input, allows to generate one output bit (zero, one or invalid) from each
single clock impulse of the LFSR based on the three last output bits of the
LFSR. An appropriate sketch and its translation table are given in Fig. 5 and
Tab. 3, where the third bit of each triplet is given out, if the two first
bits are different, otherwise no bit is given out. This generator can also be
interpreted as an output filter, which combines the three last flip-flops of
the LFSR to one output bit (including the invalid state). In half of the
output combinations a valid bit is generated per clock impulse of the LFSR.
Therefore, this extractor logic achieves either approximately
$\nicefrac{{1}}{{2}}$ efficiency for a combination with a standard LFSR or
exactly $\nicefrac{{1}}{{2}}$ for a combination with an extended LFSR.
However, the output sequence is periodic within one loop of the feeding LFSR,
yielding exactly the same output sequence with both LFSR types.

sLFSR$a_{i}$run lengthcounter$a_{i}\Longrightarrow l_{j}$translationtable$a_{i},l_{j}\Longrightarrow b_{j}$$b_{j}$ Figure 6: Pseudo-random generator using a standard LFSR in combination with a run extractor (run length interpretation) Table 4: Translation table of the run extractor (run length interpretation) run lengths $l_{j}$ of identical input bits $a_{i}\ldots a_{i+l_{j}-1}$ | output bit $b_{j}$
---|---
$=1$ | $0$ | 1
$\geq 2$ | $0$ | 0
$=1$ | $1$ | 0
$\geq 2$ | $1$ | 1

Since the extractor logic discards the bits of the primary input stream as
long as the two first of the three consecutive bits are equal, this logic
could be interpreted alternatively as a run length dependent extractor. A
valid output bit can occur only at the end of a run, where the ending run gets
broken after the last bit by the first bit of the following run with the
opposite value. This bit is denoted as the stop bit. This new run of the new
value can have either the run length one, then the next bit, following the
stop bit is opposite again. Or the new run starting with the stop bit has a
run length longer than one, then the next bit has the same value as the stop
bit.

This way it is possible to re-interpret the extraction mechanism of the
previous logic as a run length depending output extraction (Fig. 6 and Tab.
4), where the run lengths of zeros or ones generated by the LFSR are counted
first. A one is given out for a single zero bit or for a series of multiple
ones from the LFSR and a zero is given out for a single one bit or for a
series of multiple zeros from the LFSR. The difference between the two
interpretations of the extraction logic is that the first one, using the three
last bits from the LFSR generates the appropriate output bit at the beginning
of the new run (more precisely at the second bit of the new run), while the
run length interpretation reads the entire run and generates the appropriate
output bit at the end of each run. Otherwise, the two generating mechanisms
are equivalent, generating identical output streams, finally leading to the
common designation “run extractor”.

##  7 Characterization

For practical applications the length of the LFSRs should be large, resulting
in long periods of the input streams and thus long periods of the output bit
stream of the extractor and finally in a sufficient cryptographic strength of
the pseudo-random generator. So far, 160-bit LFSRs seem to be a good choice
for initialization, e.g. by an SHA-1 hash obtained from a secret password.
However, to characterize the performance of the generators, 16-bit versions of
the LFSRs are used here, which has the advantage that a full period of the
generator’s output can be examined. The following analysis characterizes the
bit streams generated by three example generators, namely

  1. a)

a von Neumann extractor driven by every two consecutive bits from a standard
16-bit LFSR with a period of $2^{16}-1$ steps (sLFSR16-vNe, see Figs. 1 and 2
in Secs. 2 and 3 and Tab. 1),

  2. b)

a three-bit extractor driven by every three consecutive bits from an extended
16-bit LFSR with a period $2^{16}$ steps (eLFSR16-3be, see Figs. 3 and 4 in
Secs. 4 and 5 and Tab. 2),

  3. c)

and a run extractor driven by single bits from a standard 16-bit LFSR with a
period of $2^{16}-1$ steps (sLFSR16-Re, see Figs. 1 and 5 or 6 in Secs. 2 and
6 and Tab. 3 resp. 4).

The basic counts and statistics of the three example generators are given in
Table 5. The ones and zeros of the resulting output bit stream are perfectly
balanced in all three cases. The sLFSR-vNe achieves $\nicefrac{{1}}{{4}}$
efficiency for long LFSRs (large number of registers $n$) and it is
$\nicefrac{{5}}{{12}}$ for the eLFSR-3be. The sLFSR-Re achieves
$\nicefrac{{1}}{{2}}$ efficiency for long LFSRs. Driving the run extractor by
an extended LFSR yields an efficiency of exactly $\nicefrac{{1}}{{2}}$.

Table 5: Basic statistics of the sLFSR16-vNe, eLFSR16-3be and sLFSR16-RLbm | sLFSR16-vNe | eLFSR16-3be | sLFSR16-Re
---|---|---|---
output period, counting … |  |  |
all states (0, 1, $\Lambda$) | 65535 | 131072 | 65535
valid states (0, 1) | 32768 | 81920 | 32768
zeros | 16384 | 40960 | 16384
ones | 16384 | 40960 | 16384
efficiency (output bits |  $\frac{16384}{65535}\approx 25\%$ |  $\frac{5}{12}\approx 42\%$ |  $\frac{32768}{65535}\approx 50\%$
per input bit) |  |  |

In [9] statistical tests of randomness are defined that any random generator
should pass. Table 6 gives the values obtained and the requirements. The
generators pass all the required tests.

Table 6: FIPS 140-1 statistical random number generator tests for randomness of the sLFSR16-vNe and eLFSR16-3be generators test |  requirement | sLFSR16 | eLFSR16 | sLFSR16
---|---|---|---|---
|  |  |  | -vNe | -3be | -Re
monobit test | $9654$ | $<X<$ | $10346$ | $10097$ | $9917$ | $10010$
poker test | $1.03$ | $<X<$ | $57.4$ | $25.958$ | $9.613$ | $12.954$
runs tests (zeros) |  |  |  |  |  |
run length 1 | $2267$ | $<X<$ | $2733$ | $2539$ | $2496$ | $2536$
run length 2 | $1079$ | $<X<$ | $1421$ | $1214$ | $1240$ | $1233$
run length 3 | $502$ | $<X<$ | $748$ | $623$ | $629$ | $625$
run length 4 | $223$ | $<X<$ | $402$ | $320$ | $324$ | $316$
run length 5 | $90$ | $<X<$ | $223$ | $158$ | $152$ | $157$
run length 6+ | $90$ | $<X<$ | $223$ | $147$ | $166$ | $153$
runs tests (ones) |  |  |  |  |  |
run length 1 | $2267$ | $<X<$ | $2733$ | $2442$ | $2515$ | $2521$
run length 2 | $1079$ | $<X<$ | $1421$ | $1296$ | $1242$ | $1244$
run length 3 | $502$ | $<X<$ | $748$ | $626$ | $656$ | $629$
run length 4 | $223$ | $<X<$ | $402$ | $313$ | $295$ | $327$
run length 5 | $90$ | $<X<$ | $223$ | $166$ | $152$ | $140$
run length 6+ | $90$ | $<X<$ | $223$ | $158$ | $147$ | $159$
long run test | $X=0$ | $0$ | $0$ | $0$
|  |  |  | all passed | all passed | all passed

Figure 7: Counts of 16-bit patterns of a) the sLFSR16-vNe, b) the eLFSR16-3be
and c) the sLFSR16-Re generators

Figure 8: Histogram of 16-bit pattern repetitions of the sLFSR16-vNe, the
eLFSR16-3be and the sLFSR16-Re generators in comparison to a binomial
distribution

In contrast to the LFSR, where all possible patterns occur exactly once in one
period of the primary bit stream, after the extraction by the three example
logics, some of the patterns occur multiple times and others do not occur in
the output stream. Fig. 7 shows how many times the particular pattern occurs
within one period of the output stream for all possible 16-bit patterns,
reaching from zero to eight, ten or six times respectively for some patterns
for the three generators. There is no indication of any deviation from a
random occurrence of the patterns.

Fig. 8 shows the histogram of the number of pattern repetitions, namely how
many of the possible 65536 patterns cannot be found in the output sequence,
how many of them occur once, how many occur twice, etc.. This can be seen as
the orthogonal projection of the data in Fig. 7. The empirical data have no
significant deviation from the expected binomial distribution for random
occurrences.

Figure 9: Run length histogram of sequences of zeros and ones for the
sLFSR16-vNe, the eLFSR16-3be and the sLFSR16-Re generators in comparison to
the expected run lengths for random termination

The observed run lengths of series of ones and zeros in Fig. 9 are well
exponentially distributed. For comparison the $0.5^{l}$ dependence of a
perfectly random bit stream with $l$ the run length of series of ones or zeros
is also shown. Even if the total number of ones and zeros in one period are
exactly balanced, their run lengths are differently distributed in detail, but
follow approximately the expected exponential decay.

Figure 10: One-sided correlation functions of the output bit stream for a) the
sLFSR16-vNe, b) the eLFSR16-3be and c) the sLFSR16-Re generators

Since the output of the generators is periodic, the correlation function is
periodic also. Furthermore, the correlation function is symmetric. Therefore,
Fig. 10 shows the correlation between zero lag and half of the period for the
three generators. Except for the correlation at lag zero, which must be one,
the correlation for all other lags is around zero. Further investigation shows
that the standard deviation of the correlation values (except for the one
value at lag zero) is $5.4\times 10^{-3}$ for the sLFSR-vNe, $3.5\times
10^{-3}$ for the eLFSR-3be and $5.5\times 10^{-3}$ for the sLFSR-Re. The
expected value for a period of 32768 steps is $5.5\times 10^{-3}$ and that for
a period of 81920 steps is $3.5\times 10^{-3}$, assuming perfect randomness of
the output streams.

Figure 11: One-sided power spectra of the output bit stream for a) the
sLFSR16-vNe, b) the eLFSR16-3be and c) the sLFSR16-Re generators

In Fig. 11 the one-sided power spectra of the three generators are shown in a
logarithmic scale. The output stream has a mean value of
$\nicefrac{{1}}{{2}}$. Therefore, the power at frequency zero is
$\nicefrac{{1}}{{4}}$. At all other frequencies the total noise power of
$\nicefrac{{1}}{{4}}$ should be distributed over all frequencies leading to an
expected power of $7.6\times 10^{-6}$ for a period of 32768 steps and
$3.1\times 10^{-6}$ for a period of 81920 steps. The shown spectra of the
investigated generators comply with a fully random bit stream.

Figure 12: Linear complexity profiles of the sLFSR16-vNe, the eLFSR16-3be and
the sLFSR16-Re generators in comparison to an ideal random sequence generator

With the Berlekamp-Massey algorithm [1] the linear complexity $L$ of any
subsequence of the generated bit streams can be derived as a function of the
length $l$ of the subsequences, giving the linear complexity profile. Fig. 12
shows the linear complexity profiles for the three example generators, which
all follow the ideal $L=\nicefrac{{l}}{{2}}$ relation over a full period of
their output streams.

Figure 13: Histogram of number of required input bits to generate the next
valid output bit for the sLFSR16-vNe, the eLFSR16-3be and the sLFSR16-Re
generators in comparison to the expected lengths for random termination

A disadvantage of the investigated generators in practical implementation with
hardware circuits is that the number of input bits required to generate the
next output bit is not known in advance and changes randomly from one output
bit to the next. However, the varying number of primary bits from the LFSRs
needed to produce one valid output bit, on the other hand is an advantage in
strengthening the bit stream in a cryptographic sense, because the output
stream gives no indication of how many bits of the input stream have been
discarded between successive output bits.

Fig. 13 shows the distribution of the number of primary bits required to
generate the next output bit for the three generators investigated. Even if
the mean values are known, the individual number of steps required is random
with an exponential distribution, which is also shown as a reference in the
diagram. While the sLFSR16-vNe requires at least two steps, the eLFSR16-3be
generates two output bits at once in half of the input combinations.
Therefore, there are also cases where no additional step of the eLFSR is
required. However, this particular case, is outside the exponential law of the
other values in the diagram. The sLFSR16-Re generator reflects exactly the
distribution of the run lengths of the LFSR and, therefore, perfectly follows
the exponential decay until it reaches 16, which is the maximum possible run
length corresponding to the length of the feeding LFSR. The slopes of the
distributions directly correspond to the efficiency of the generators given in
Table 5.

##  8 Conclusion

The use of extractors or appropriate translation tables to obtain a shrunken
bit stream from a primary bit stream of an LFSR combines good statistical
properties of the generated pseudo-random bit stream, such as a balanced
distribution of ones and zeros, random run lengths and low correlation with a
large linear complexity. Therefore, such combinations of an LFSR with
extraction logics have potential as pseudo-random generators for cryptographic
key streams. The disadvantage of such an extractor is that it produces a
shorter output stream with a significant number of discarded bits. At the same
time, this is an advantage for its cryptographic strength, as it makes it
difficult to reconstruct the primary stream from the output data.

The von Neumann extractor achieves about $25\%$ efficiency, meaning it
generates one output bit from four bits generated by the LFSR on average. To
maximize the period of the output stream, the von Neumann extractor is fed by
a standard $n$ bit long LFSR with $2^{n}-1$ internal states.

With a similar concept, the three-bit extractor shown here, also has excellent
statistical properties and has a higher efficiency of nearly $42\%$ in
generating the output stream, while again the cryptographic strength must be
obtained by an unpredictable number of input bits discarded between two
successive output bits and a minimum coherence between the input and the
output stream by an appropriate translation table. With an appropriate
translation table, a specific output pattern can be achieved from different
inputs, which ideally have different lengths of the primary bit stream and a
high variation in their input bit sequences. Since the translation table is
critical to the effort of breaking the pseudo-random generator, it could be
subject to updates, if it is later found to be weak. To obtain maximum periods
of the output stream, the three-bit extractor is fed by an extended $n$ bit
long LFSR with $2^{n}$ internal states.

The concept can be further extended to a four-bit extractor, again applied to
a standard LFSR. In this case the efficiency can be further increased to
$\nicefrac{{17}}{{32}}\approx 53\%$. To avoid weakening the cryptographic
strength, an appropriate translation table is required, which should be
designed with special care, which may be added to the present investigations
later.

With $50\%$, the run extractor reaches the highest efficiency among the three
generator logics investigated here, with otherwise perfect random statistical
properties. On the contrary, a higher efficiency in using the primary input
bits to form the output stream comes with a lower cryptographic strength.
Since each bit of the output stream is obtained from a run of either zeros or
ones, the run extractor is significantly weaker than the other two extraction
logics investigated. Only the lengths of the respective runs are unknown.
Since short runs are more probable than long runs, attacks could first try
combinations of short runs and successively test longer runs, which then are
less probable and have less possible bit variations also. Even if this
extractor fulfills a certain minimum of cryptographic strength, it is not
suitable for applications with serious demands in its cryptographic strength.
However, the present investigation had its focus more on the efficiency of the
respective extractors and the quality of the generated pseudo-random bit
streams than on their cryptographic strengths.

The Python programs used for this test with the three generator logics are
openly available at http://www.nambis.de/publications/arxiv24a.html.

## References

  * [1] J L Massey.  Shift-register synthesis and BCH decoding.  IEEE Trans. Information Theory, pages 122–127, 1969.
  * [2] John von Neumann.  Various techniques used in connection with random digits.  J. Research Nat. Bur. Stand., Appl. Math. Series, 12:36–38, 1951.
  * [3] Willi Meier and Othmar Staffelbach.  The self-shrinking generator.  In EUROCRYPT, pages 205–214, 1994.
  * [4] P Elias.  The efficient construction of an unbiased random sequence.  The Annals of Mathematical Statistics, 43(3):865–870, 1972.
  * [5] Y Peres.  Iterating von Neumann’s procedure for extracting random bits.  The Annals of Statistics, 20(1):590–597, 1992.
  * [6] P P Deepthi, Deepa Sara John, and P S Sathidevi.  Design and analysis of a highly secure stream cipher based on linear feedback shift register.  Computers and Electrical Engineering, 35(2):235–243, 2009.
  * [7] F Masoodi, S Alam, and M U Bokhari.  An analysis of linear feedback shift registers in stream ciphers.  International Journal of Computer Applications, 46(17):46–49, 2012\.
  * [8] Roy Ward and Tim Molteno.  Table of linear feedback shift registers, 2007.
  * [9] National Institute of Standards and Technology, Information Technology Laboratory.  Federal information processing standards publication 140-1, security requirements for cryptographic modules, 1994.