Update package generator that employs genetic evolution to determine bank order

• US 7,434,216 B1
• Filed: 11/25/2003
• Issued: 10/07/2008
• Est. Priority Date: 11/25/2002
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lilley, Patrick C., McGhee, LaShawn, O'Neill, Patrick, O'Neill, Brian
• Primary Examiner(s): Bullock, Jr.; Lewis A.
• Assistant Examiner(s): YAARY, MICHAEL D
• Application Number:
  US10/721,658
• Time in Patent Office: 1,778 Days
• Field of Search: 717168-178, 711/216, 711/217, 711/158
• US Class Current: 717/169
• CPC Class Codes: G06F 8/658 Incremental updates; Differential updates

Abstract

Disclosed herein is an update package generator which may employ a bank order determination module to determine an optimum bank order of memory banks of a binary image of at least one of firmware and software. The bank order may subsequently be employed in generation of an update package, wherein the size of the update package generated by the generator may be minimized. A bank order determination unit may selectively employ one of genetic algorithms and differential evolution techniques to determine an optimum bank order. Other parameters may also be employed in the generator. The generator may also be selectively optimized to employ at least one genetic evolution technique.

Claims

1. A system for generating difference information between a first binary image of an electronic device and a second binary image of the electronic device, the system comprising:

a bank order determination unit adapted to employ at least one differential evolution technique to determine a bank order of updating electronic device memory comprising a plurality of banks, the bank order determination unit adapted to employ genomes to represent bank orders of memory banks of the electronic device and to represent other additional parameters;

wherein the first binary image and the second binary image comprise at least one of firmware and software in memory banks of the electronic device;

wherein the system is adapted to determine optimum values for the bank order and other additional parameters employing the at least one differential evolution technique, the optimum values for the bank order and other additional parameters making the update package compact to the greatest degree attainable by the system; and

wherein the determined bank order and the difference information are transmitted to and processed by the electronic device to update memory in the electronic device.

2. The system according to claim 1, wherein the other additional parameters are selected from instructions associated with at least one of run-length encoding (RLE) instructions, copy (CPY) instructions, and duplicate (DUP) instructions.

3. The system according to claim 2, further comprising an evolve population module adapted to evolve a population of genomes by at least one generation, wherein the evolve population module is also adapted to evaluate the population and sort the population before evolving the population to subsequent generations, and the evolve population module is adapted to selectively create crossover genomes as part of an evolution process and store the crossover genomes for subsequent processing.

4. A method for generating an update package comprising difference information for updating at least one of firmware and software in memory of an electronic device, the memory comprising a plurality of banks, the method comprising:

determining an optimal bank order for processing images of the memory during generation of difference information, using at least one differential evolution technique employing at least one genetic computation technique comprising;

creating a new population of genomes;

evaluating the population of genomes;

evolving the population of genomes; and

repeating evaluating and evolving the population at least until;

a determination is made that there are no other results to be found,

a threshold is reached, or

a user cancels generation of the genomes;

employing the optimal bank order to generate the update package; and

wherein the optimal bank order makes the update package compact to the greatest degree attainable by the method.

5. The method according to claim 4, wherein creating a new population comprises:

adding seeds to the population of genomes, the seeds comprising at least one of a forward bank order seed and a backward bank order seed; and

filling the population with randomly created genomes.

6. The method according to claim 4, wherein creating a new population comprises:

seeding the population of genomes by building a forward bank order for a required number of banks;

selectively storing a CRC value for the forward bank order for subsequent access;

placing the forward bank order into the genomes;

building a reverse order of banks;

storing the CRC value for the reverse bank order; and

placing the reverse order of banks into the genomes.

7. The method according to claim 4, wherein evaluating the population of genomes comprises testing for a best desired outcome.

8. The method according to claim 7, wherein evaluating the population of genomes further comprises at least one of determining weights for the genomes and determining an evaluation function adapted to be employed to compare and selectively order the genomes in the population.

9. The method according to claim 4, wherein evolving the population of genomes comprises:

mating parents to create at least one of crossover and mutated genomes; and

filling the population of genomes with randomly created genomes.

10. The method according to claim 4, wherein, during the evolving of the population of genomes, two elite genomes are employed as parents for a new genome and a crossover technique is employed by the bank order determination unit after ensuring that both parents are not identical.

11. The method according to claim 10, wherein the parent genomes are mated by mixing respective parent genome bank order weights.

12. The method according to claim 4, wherein an elite genome and a non-elite genome are employed as parents for a new genome.

13. The method according to claim 4, wherein two genomes comprising at least one of elite and non-elite genomes are randomly selected as parents to create a new genome.

14. A generator for generating an update package comprising difference information for updating at least one of firmware and software in memory of an electronic device, the memory comprising a plurality of banks, the generator comprising:

at least one processor communicatively coupled to the electronic device, the at least one processor operating to perform a method comprising the steps of, at least;

determining an optimal bank order for processing images of the memory during generation of difference information, using at least one differential evolution technique employing at least one genetic computation technique comprising;

creating a new population of genomes;

evaluating the population of genomes;

evolving the population of genomes; and

repeating evaluating and evolving the population at least until;

a determination is made that there are no other results to be found,

a threshold is reached, or

a user cancels generation of the genomes;

employing the optimal bank order to generate the update package; and

wherein the optimal bank order makes the update package compact to the greatest degree attainable by the method.

15. The generator according to claim 14, wherein creating a new population comprises:

adding seeds to the population of genomes, the seeds comprising at least one of a forward bank order seed and a backward bank order seed; and

filling the population with randomly created genomes.

16. The generator according to claim 14, wherein creating a new population comprises:

seeding the population of genomes by building a forward bank order for a required number of banks;

selectively storing a CRC value for the forward bank order for subsequent access;

placing the forward bank order into the genomes;

building a reverse order of banks;

storing the CRC value for the reverse bank order; and

placing the reverse order of banks into the genomes.

17. The generator according to claim 14, wherein evaluating the population of genomes comprises testing for a best desired outcome.

18. The generator according to claim 17, wherein evaluating the population of genomes comprises at least one of determining weights for the genomes and determining an evaluation function adapted to be employed to compare and selectively order the genomes in the population.

19. The generator according to claim 14, wherein evolving the population of genomes comprises:

mating parents to create at least one of crossover and mutated genomes; and

filling the population of genomes with randomly created genomes.

20. The generator according to claim 14, wherein, during the evolving of the population of genomes, two elite genomes are employed as parents for a new genome and a crossover technique is employed after ensuring that both parents are not identical.

21. The generator according to claim 14, wherein an elite genome and a non-elite genome are employed as parents for a new genome.