Genetic algorithm for microcode compression

• US 7,451,121 B2
• Filed: 09/27/2005
• Issued: 11/11/2008
• Est. Priority Date: 09/27/2005
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wu, Youfeng, Breternitz, Mauricio Jr.
• Primary Examiner(s): Vincent; David
• Assistant Examiner(s): COUGHLAN, PETER D
• Application Number:
  US11/237,562
• Publication Number:
  US 20070094164A1
• Time in Patent Office: 1,141 Days
• Field of Search: 706/13, 706/14, 706/15, 706/16
• US Class Current: 706/13
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method to compress microcode utilizing a genetic algorithm includes generating a population of chromosomes, each chromosome including one or more elements that indicate a cluster to which a portion of microcode memory belongs. The method further includes determining a fitness value of each chromosome and modifying the population of chromosomes based on the fitness values of the chromosomes to generate a new population of chromosomes. In addition, the method includes compressing the microcode memory using a cluster-based compression technique, wherein clusters are selected according to a chromosome from the new population with the best fitness value. Other embodiments are also disclosed.

Claims

1. A method, comprising:

generating a population of chromosomes, each chromosome including one or more elements that indicate a cluster to which a portion of microcode memory belongs;

determining a fitness value of each chromosome, where the fitness value is a function of a number of columns in the microcode memory, a number of bits in each column, a number of clusters that the columns in the microcode memory are clustered into, a number of columns in each cluster, and a number of unique patterns in each cluster;

modifying the population of chromosomes based on the fitness values of the chromosomes to generate a new population of chromosomes; and

compressing the microcode memory using a cluster-based compression technique, wherein clusters are selected according to a chromosome from the new population with the best fitness.

2. The method of claim 1, wherein modifying the population of chromosomes further comprises:

selecting a chromosome with the highest fitness value of the population to keep in the new population of chromosomes;

removing one or more chromosome having a fitness value in the lower half of the fitness values of the population;

crossing-over one or more pairs of chromosomes to produce permutations of the chromosomes; and

mutating one or more chromosomes to produce new chromosomes.

3. The method of claim 2, wherein mutating one or more chromosomes further comprises changing the value of each element in the one or more chromosomes with a first probability for chromosomes with a fitness value in the top half of the fitness values of the population and a second probability that is higher than the first probability for chromosomes with a fitness value in the bottom half of the fitness values of the population.

4. The method of claim 3, wherein the first probability is 5% and the second probability is 10%.

5. The method of claim 1, wherein determining a fitness value and modifying the population are repeated to improve the fitness values of the chromosomes.

6. The method of claim 1, wherein determining a fitness value and modifying the population are repeated until a chromosome with a fitness value exceeding a threshold fitness value is found.

7. The method of claim 5, wherein determining the fitness value further comprises applying an objective function to each chromosome that identifies the microcode storage saved by each chromosome.

8. The method of claim 1, wherein the microcode storage is microcode read only memory (UROM).

9. The method of claim 1, wherein the chromosome is a data structure including a string of bits.

10. A machine-accessible medium having stored thereon data representing sets of instructions that, when executed by a machine, cause the machine to perform operations comprising:

generating a first population of chromosomes, each chromosome including one or more elements that indicate a cluster to which a portion of microcode memory is assigned;

determining a fitness value of each chromosome, where the fitness value is a function of a number of columns in the microcode memory, a number of bits in each column, a number of clusters that the columns in the microcode memory are clustered into, a number of columns in each cluster, and a number of unique patterns in each cluster;

generating a second population of chromosomes by modifying the first population of chromosomes based on the fitness values of the first population of chromosomes; and

compressing the microcode memory using a cluster-based compression technique, wherein clusters are selected according to a chromosome from the second population with the best fitness value.

11. The machine-accessible medium of claim 10, wherein generating the second population of chromosomes further comprises:

selecting a chromosome from the first population with the highest fitness value of fitness values of the first population to include in the second population;

excluding from the second population one or more chromosome having a fitness value in the lower half of the fitness values of the first population;

crossing-over one or more pairs of chromosomes from the first population to produce permutations of the one or more pairs of chromosomes to include in the second population; and

mutating one or more chromosomes to produce new chromosomes to include in the second population.

12. The machine-accessible medium of claim 11, wherein mutating one or more chromosomes further comprises changing the value of each element in the one or more chromosomes with a first probability for chromosomes with a fitness value in the top half of the fitness values of the first population and a second probability that is higher than the first probability for chromosomes with a fitness value in the bottom half of the fitness values of the first population.

13. The machine-accessible medium of claim 10, wherein determining a fitness value further comprises applying an objective function to each chromosome that identifies microcode storage saved by each chromosome.

14. The machine-accessible medium of claim 10, wherein the microcode storage is microcode read only memory (UROM).

15. The machine-accessible medium of claim 10, wherein determining a fitness value and generating a second population are repeated to improve the fitness values.

16. A system, comprising:

a microcode read only memory (UROM); and

a processor coupled with the UROM memory, the processor to;

generate a population of chromosomes, each chromosome including one or more elements that indicate a cluster to which a portion of microcode memory belongs;

determine a fitness value of each chromosome, where the fitness value is a function of a number of columns in the microcode memory, a number of bits in each column, a number of clusters that the columns in the microcode memory are clustered into, a number of columns in each cluster, and a number of unique patterns in each cluster;

modify the population of chromosomes based on the fitness values of the chromosomes to generate a new population of chromosomes; and

compress the microcode memory using a cluster-based compression technique, wherein clusters are selected according to a chromosome from the new population with the best fitness value.

17. The system of claim 16, wherein modifying the population of chromosomes further comprises:

selecting a chromosome with the highest fitness value of the fitness values of the population to keep in the new population;

removing one or more chromosomes having fitness values in the lower half of the fitness values of the population;

crossing-over one or more pairs of chromosomes to produce permutations of the chromosomes; and

mutating one or more chromosomes to produce new chromosomes.

18. The system of claim 17, wherein mutating one or more chromosomes further comprises changing the value of each element in the one or more chromosomes with a first probability for chromosomes with a fitness value in the top half of the fitness values of the population and a second probability that is higher than the first probability for chromosomes with a fitness value in the bottom half of the fitness values of the population.

19. The system of claim 16, wherein determining the fitness value and modifying the population are repeated until a chromosome with a fitness value exceeding a threshold fitness value is found.

20. The system of claim 16, wherein the chromosome is a data structure including a string of bits.