Memory re-implementation for field programmable gate arrays

• US 20050093571A1
• Filed: 02/23/2004
• Published: 05/05/2005
• Est. Priority Date: 11/05/2003
• Status: Active Grant

• Current Assignee: Siemens Industry Software Inc. (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Ding, Yuzheng, Liu, Lung-Tien, Chou, Nan-Chi, Suaris, Peter Ramyalal
• Granted Patent: US 7,251,803 B2
• Time in Patent Office: Days
• US Class Current: 326/37
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]

Abstract

Memory modules implemented on an FPGA device are re-implemented to improve the performance of the device, such as to reduce logic delays. One or more logic blocks of the FPGA device that realize the logic function of a memory module or portion of a memory module are desirably selected. Based on the outcome of a timing analysis, the most critical signal pin of the selected logic blocks may be identified. Methods of deriving the memory module re-implementation for various types of the most critical pins are disclosed. Procedures are described for integrating physical timing analysis, memory transformation, placement, and routing, as well as for the selection of logic blocks for re-implementation.

Claims

1. A method of re-implementing at least one memory module having an undesirable timing delay, the at least one memory module being on an FPGA device, the FPGA device comprising generic logic blocks and dedicated logic blocks, the at least one memory module being implemented by a first set of at least one of the logic blocks, the at least one logic block of said first set has at least one critical pin, the method comprising:

(a) identifying the at least one memory module;

(b) selecting a second set of logic blocks for use in re-implementing said at least one memory module, at least a first logic block of the said second set having a pin that is logically equivalent to said at least one critical pin of the at least one logic block of said first set, the first logic block of the second set being non-identical to the at least one logic block of the first set; and

(c) selectively re-implementing the at least one memory module using the second set of logic blocks in the event that re-implementation using the second set of logic blocks reduces the undesirable timing delay of the at least one memory module.

2. A method according to claim 1 wherein the second set comprises at least one dedicated memory logic block and at least one generic logic block.

3. A method according to claim 1 wherein the first set comprises only generic logic blocks and the second set comprises at least one dedicated memory logic block.

4. A method according to claim 1 wherein the first set comprises at least one dedicated memory logic block and the second set comprises at least one more dedicated memory logic block than the said first set.

5. A method according to claim 1 wherein the first set comprises at least one dedicated memory logic block and the second set comprises only generic logic blocks.

6. A method according to claim 1 wherein the act of identifying the at least one memory module comprises performing physical timing analysis on at least said one memory module, the method further comprising performing physical timing analysis on said at least one memory module to identify the at least one critical pin of said first set of at least one logic block, and wherein the method further comprises performing physical timing analysis on the re-implemented memory module using the second set of logic blocks prior to selecting the re-implementation of the at least one memory module using the second set of logic blocks.

7. A method according to claim 1 comprising the act of reversing the re-implementation to an implementation of the at least one memory module using the first set of logic blocks in the event the undesirable timing delay of the at least one memory module is not sufficiently reduced upon re-implementation using the second set of logic blocks.

8. A method according to claim 1 comprising repeating the acts of claim 1 for one or more additional sets of logic blocks which are non-identical to one another and which are non-identical to the first and second sets.

9. A method according to claim 8 in which the selectively re-implementing act comprises the act of selecting a set of logic blocks for re-implementing the at least one memory module which eliminates the undesirable timing delay.

10. A method according to claim 8 comprising the act of reversing a subsequent re-implementation of the at least one memory module to a prior implementation or prior re-implementation in the event the undesirable timing delay of the at least one memory module is not sufficiently reduced by the subsequent re-implementation of the at least one memory module.

11. A computer programmed to implement the method of claim 1.

12. Computer readable media programmed with computer readable instructions to carry out the method of claim 1.

13. For use in a computer system, a design database of FPGA programming instructions stored on computer readable media for a re-implemented memory module which has been re-implemented in accordance with the method of claim 1.

14. A method of implementing one or more memory modules on an FPGA device comprising logic blocks, the method comprising:

(a) generating an initial implementation of the one or more memory modules;

(b) performing physical timing analysis on the implementation;

(c) selecting one or more logic blocks on the FPGA that implement a memory module, or a part of a memory module;

(d) re-implementing, for the benefit of circuit delay reduction, the memory module or a part of the memory module, the act of re-implementing comprising replacing at least one of the selected one or more logic blocks with at least one different replacement logic block to provide a modified set of one or more logic blocks and rearranging the modified set of logic blocks based on physical timing analysis; and

(e) re-connecting the modified set of logic blocks of the re-implemented memory module or part of the memory module on the FPGA device based on physical timing analysis.

15. A method according to claim 14 comprising user identification of the said one or more logic blocks in (c) for re-implementation.

16. A method according to claim 14 further comprising the automatic selection of said one or more logic blocks in (c) for re-implementation, based on timing analysis.

17. A method according to claim 14 further comprising selectively reversing the re-implementation.

18. A method according to claim 14 further comprising the repeated application of the (b), (c), (d) and (e) acts of claim 14.

19. A method according to claim 18 comprising the act of reversing a subsequent re-implementation of the at least one memory module to a prior implementation or prior re-implementation.

20. A computer programmed to implement the method of claim 14.

21. Computer readable media programmed with computer readable instructions to carry out the method of claim 14.

22. For use in a computer system, a design database of FPGA programming instructions stored on computer readable media for a re-implemented memory module which has been re-implemented in accordance with the method of claim 14.

23. A method of re-implementing a memory module, or part of a memory module, that has been implemented on an FPGA device at least in part by a first dedicated memory logic block, the FPGA device comprising plural logic blocks including the first dedicated memory logic block, the method comprising:

(a) identifying the most critical pin of the first dedicated memory logic block;

(b) separating the said most critical pin from the said first dedicated memory logic block, the act of separating comprising substituting two or more logic blocks on the FPGA for said first dedicated memory block, the substituted two or more logic blocks realizing the same logic functions of the memory module or the said part of the memory module, wherein the substituted two or more logic blocks may realize the function of a portion of said first dedicated memory logic block; and

(c) placing the substituted two or more logic blocks to available locations on the FPGA device and re-connecting the substituted two or more logic blocks, based on timing analysis, to thereby re-implement the memory module and so as to reduce timing delay.

24. The method according to claim 23 wherein the act of identifying the most critical pin comprises a user identification of the most critical pin.

25. The method according to claim 23 wherein the act of identifying the most critical pin comprises the act of automatically selecting the most critical pin based upon physical timing analysis.

26. The method according to claim 23 further comprising the repeated application of the acts (a), (b) and (c) of claim 23 on further substitute groups of two or more logic blocks.

27. The method according to claim 23 comprising performing the acts of claim 23 for at least one critical pin in addition to the most critical pin.

28. A method of re-implementing a memory module, or a part of a memory module, that has been implemented on an FPGA device by a first dedicated memory logic block, and whose most critical pin is a data input or output, the FPGA device comprising dedicated and generic logic blocks including the first dedicated memory logic block, the method comprising:

(a) dividing the said memory module or the said part of a memory module into at least two parts, with a first part comprising the memory cells accessed via the said most critical pin, and the second part comprising the memory cells accessed via other data pins other than the said most critical pin;

(b) re-implementing the second part using the first dedicated memory logic block;

(c) re-implementing the first part using logic blocks other than the first dedicated memory logic block; and

(d) placing the logic blocks implementing the first part to advantageous locations on the FPGA device, and re-connecting the signals, based on physical timing analysis.

29. A method according to claim 28 further comprising using at least one dedicated memory logic block other than the first dedicated memory logic block for the re-implementing the first part act (c) of claim 28.

30. A method according to claim 28 further comprising using generic logic blocks without using any dedicated memory logic blocks for the re-implementing the first part act (c) of claim 28.

31. The method according to claim 28 comprising performing the acts of claim 28 for at least one additional critical data input or output pin.

32. A method of re-implementing a memory module, or a part of a memory module, that has been implemented on an FPGA device by a first dedicated memory logic block, and whose most critical pin is a read address, the FPGA device comprising dedicated and generic logic blocks including the first dedicated memory logic block, the method comprising:

(a) dividing the said memory module or the said part of a memory module into the at least two parts, with a first part (Part

     1) comprising the memory cells which are accessible when the address signal at the critical pin and address corresponds to a logic value 0, and a second part (Part

     2) comprising the memory cells which are accessible when the address signal at the critical pin read address corresponds to a logic value 1;

(b) re-implementing the first part (Part

     1) and the second (Part

     2) using plural logic blocks to integrate the functioning of the first part (Part

     1) and second part (Part

     2) as the re-implemented memory module or re-implemented part of the memory module;

(c) providing a multiplexer, which is realized by a logic block or a portion of a logic block, for each data output related to the said address signal to select the corresponding data output from the first part (Part

     1) when the said address signal corresponds to a logic value 0, or from the second part (Part

     2) when the said address signal corresponds to a logic value 1; and

(d) placing the logic blocks comprising the memory module or part of the memory module to available locations on the FPGA, and re-connecting the signals based on timing analysis to minimize circuit delay.

33. The method according to claim 32 further comprising performing the re-implementing act of (b) for the first part (Part 1) using at least one dedicated memory logic block for the first part (Part 1).

34. The method according to claim 33 further comprising performing the re-implementing act of (b) for the second part (Part 2) using only generic logic blocks for the second part (Part 2).

35. The method according to claim 34 further comprising performing the re-implementing act of (b) for the second part (Part 2) using at least one dedicated logic block for the second part (Part 2).

36. The method according to claim 32 further comprising performing the re-implementing act of (b) for the second part (Part 2) using at least one dedicated memory logic block for the second part (Part 2).

37. The method according to claim 36 further comprising performing the re-implementing act of (b) for the first part (Part 1) using only generic logic blocks for the first part (Part 1).

38. The method according to claim 32 further comprising performing the re-implementing act of (b) for the first part (Part 1) using plural generic logic blocks for the first part (Part 1).

39. The method according to claim 32 further comprising performing the re-implementing act of (b) for the second part (Part 2) using plural generic logic blocks for the second part (Part 2).

40. The method according to claim 32 comprising performing the acts of claim 32 for at least one additional critical read address pin.

41. A method according to claim 32 wherein the first dedicated memory logic block is used to re-implement either the first part (Part 1) or the second part (Part 2).

45. A method according to claim 42 comprising performing the acts of claim 37 for at least one additional critical pin.

42. A method of re-implementing a memory module, or a part of a memory module, that has been implemented on an FPGA by a dedicated memory block, and wherein the most critical pin is other than a data input pin or data output pin or read address pin, the FPGA device comprising distributed generic logic blocks and dedicated memory blocks, the method comprising:

(a) re-implementing the said memory module or the said part of a memory module with the re-implementation of said memory module or the said part of said memory module comprising generic logic blocks and without using dedicated memory logic blocks; and

(b) placing the logic blocks that re-implement the memory module or the said part of a memory module on the FPGA device and reconnecting the signal, based on timing analysis;

so as to reduce circuit delay.

43. A method according to claim 42 wherein the most critical pin is a write enable signal receiving pin.

44. A method according to claim 42 wherein the most critical pin is a write address pin.

46. A method of re-implementing a memory module, or a part of a memory module, that has been implemented on an FPGA device, the FPGA device comprising dedicated and generic logic blocks, the memory module, or part of a memory module, having been implemented by a first set of one or more generic logic blocks, the method comprising:

(a) identifying additional generic logic blocks, which together with the first set of generic logic blocks, implement the said memory module or the said part of a memory module;

(b) re-implementing the said memory module or the said part of a memory module using one or more logic blocks comprising at least one dedicated logic block; and

(c) placing the logic blocks used to re-implement the memory module or the said part of a memory module on the FPGA device, and re-connecting the signals, based on physical timing analysis, so as to reduce circuit delay.

47. A method according to claim 46, wherein the re-implementing act (b) of claim 46 further comprises:

(a) re-implementing the said memory module or the said part of a memory module using one or more dedicated memory logic blocks;

(b) placing the one or more dedicated memory logic blocks used to re-implement the memory module or the said part of a memory module to available locations on the FPGA device, and re-connecting the signals, based on physical timing analysis, so as to reduce circuit delay;

(c) identifying the most critical pin of the said one or more dedicated memory logic blocks, and a first dedicated memory logic block that has the most critical pin;

(d) re-implementing the said first dedicated memory logic block using a second set of logic blocks containing at least one non-identical logic block to said first dedicated memory logic block; and

(e) placing the said second set of logic blocks used to re-implement the said first dedicated memory logic block on the FPGA device, and re-connecting the signals, based on physical timing analysis, so as to reduce circuit delay.

48. A method according to claim 47 wherein the act of identifying the most critical pin and the first dedicated memory logic block that has the most critical pin comprises physical timing analysis of the said one or more dedicated memory logic blocks.

49. A method according to claim 47 comprising repeating the acts (c) and (d) of claim 47 for one or more additional critical pins of additional dedicated memory logic blocks which are non-identical to one another and which are non-identical to the first most critical pin and the first dedicated memory logic block, wherein the combined set of logic blocks that re-implements the said memory module or said portion of memory module comprises at least one dedicated memory logic block.

50. A method according to claim 47 wherein said most critical pin is a data input or output pin of the said first dedicated memory logic block, the re-implementing act (c) of claim 47 for the first dedicated memory logic block comprising:

(a) dividing the function of said first dedicated memory logic block into at least two parts, with a first part comprising the memory cells accessed via the said most critical pin, and the second part comprising the memory cells accessed via other data pins other than the said most critical pin;

(b) re-implementing the second part using the first dedicated memory logic block;

(c) re-implementing the first part using logic blocks other than the first dedicated memory logic block; and

(d) placing the logic blocks implementing the first part to advantageous locations on the FPGA device, and re-connecting the signals, based on physical timing analysis.

51. A method according to claim 50, further comprising using at least one dedicated memory logic block for the re-implementing act (c) of claim 50.

52. A method according to claim 50, further comprising using generic logic blocks without using dedicated memory logic blocks for the re-implementing act (c) of claim 50.

53. The method according to claim 50 comprising performing the acts of claim 50 for at least one additional critical data input or output pin.

54. A method according to claim 47 wherein said most critical pin is a read address of the said first dedicated memory logic block, the re-implementing act (c) of claim 47 for the first dedicated memory logic block comprising:

(a) dividing the function of said first dedicated memory logic block into at least two parts, with a first part (Part

     1) comprising the memory cells which are accessible when the address signal at the critical pin and address corresponds to a logic value 0, and the second part (Part

     2) comprising the memory cells which are accessible when the address signal at the critical pin read address corresponds to a logic value 1;

(b) re-implementing the first part (Part

     1) and second part (Part

     2) using plural logic blocks to integrate the functioning of the first part (Part

     1) and second part (Part

     2) as the re-implemented memory module or re-implemented part of the memory module;

(c) providing a multiplexer, which is realized by a logic block or a portion of a logic block, for each data output related to the said address signal to select the corresponding data output from the first part (Part

     1) when the said address signal corresponds to a logic value 0, or from the second part (Part

     2) when the said address signal corresponds to a logic value 1; and

(d) placing the logic blocks comprising the memory module or part of the memory module to available locations on the FPGA, and re-connecting the signals;

based on timing analysis to minimize circuit delay.

55. The method according to claim 54 further comprising performing the re-implementing act of (b) for the first part (Part 1) using at least one dedicated memory logic block for the first part (Part 1).

56. The method according to claim 54 further comprising performing the re-implementing act of (b) for the second part (Part 2) using at least one dedicated memory logic block.

57. The method according to claim 54 further comprising performing the re-implementing act of (b) for the first part (Part 1) using generic logic blocks for the first part (Part 1).

58. The method according to claim 54 further comprising performing the re-implementing act of (b) for the second part (Part 2) using generic logic blocks for the second part (Part 2).

59. The method according to claim 54 comprising performing the acts of claim 54 for at least one additional critical read address pin.

60. A method according to claim 46, wherein said most critical pin is a signal pin other than a data input, or data output, or read address, of the said first dedicated memory logic block, the re-implementing act of (c) for the first dedicated memory logic block comprising:

(a) re-implementing the said memory module or the said part of a memory module with the re-implementation comprising generic logic blocks and without using dedicated memory logic blocks; and

(b) placing the logic blocks that re-implement the memory module or the said part of a memory module on the FPGA device and reconnecting the signals, based on timing analysis, so as to reduce circuit delay.

61. A method according to claim 60 comprising performing the acts of claim 60 for at least one additional critical pin.

62. A computer programmed to implement the method of claim 47.

63. Computer readable media programmed with computer readable instructions to carry out the method of claim 47.

64. For use in a computer system, a design database of FPGA programming instructions stored on computer readable media for a re-implemented memory module which has been re-implemented in accordance with the method of claim 47.

65. An apparatus for re-implementing a memory module, or re-implementing a part of a memory module, that has been implemented on an FPGA device, the FPGA device comprising logic blocks, the apparatus comprising:

(a) means for providing an initial implementation of the memory module or part of a memory module using a first set of logic blocks, the first set including at least one logic block; and

(b) means for re-implementing the memory module or part of a memory module using a second set of logic blocks which is not identical to the first set of logic blocks based on physical timing analysis and wherein the re-implementation reduces timing delay arising from the memory module or part of the memory module that is being re-implemented.