Dynamic bus arbitration priority and task switching based on shared memory fullness in a multi-processor system

• US 6,157,989 A
• Filed: 06/03/1998
• Issued: 12/05/2000
• Est. Priority Date: 06/03/1998
• Status: Expired due to Term

• Current Assignee: North Star Innovations Inc. (Wi-LAN Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Collins, Eric S., Lindsley, Brett L., Hill, Reginald J.
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): Anderson, Matthew D.
• Application Number:
  US09/089,721
• Time in Patent Office: 916 Days
• Field of Search: 711/151, 711/158, 709/103, 395/673, 395/287, 710/57, 710/116
• US Class Current: 711/151
• CPC Class Codes: G06F 13/18 based on priority control G06F13/1605 takes precedence

Abstract

An arbitration and task switching technique in a real-time multiprocessor data processing system (20) having a common bus (32) and a segmented shared memory (30), where fullness of memory segments of the shared memory (30) is used as a measurement for arbitration and task switching priorities. A bus request mechanism in each of the processors dynamically calculates normalized priority values based on relative needs across the system (20). The normalized priority calculation is based on monitoring the fullness of memory segments of the shared memory (30) associated with each processor (24, 26, 28) of the system (20). Using this normalized priority calculation, the bus access order and bus bandwidth are optimally allocated according to tasks executed by the processors (24, 26, 28). Also, the normalized priority calculation and a preprogrammed threshold is used to control task switching in the multi-processor system (20).

Claims

1. A bus master device for coupling to a shared memory via a common bus, the common bus adapted to couple to another bus master device, comprising:

an execution unit having an input terminal for receiving a current priority signal which indicates a degree of fullness of a memory segment located in the shared memory, and an output terminal coupled to an output terminal of the bus master device, said execution unit periodically arbitrating for usage of the common bus in response to an internal operation by providing said current priority signal to said output terminal; and

a snoop logic block having an input terminal coupled to the common bus, and an output terminal coupled to said input terminal of said execution unit for providing said current priority signal thereto, wherein said snoop logic block monitors a fullness state of said memory segment and changes said current priority signal in response to the another bus master device accessing said memory segment.

2. The bus master device of claim 1 wherein said execution unit further includes a second input terminal for receiving an arbitration winner signal, and wherein the bus master device performs an access to the shared memory via the common bus in response to an activation of the arbitration winner signal.

3. The bus master device of claim 1 wherein the internal operation comprises signal processing of data stored in the memory segment.

4. The bus master device of claim 1 wherein the bus master device is characterized as being a monolithic integrated circuit separate from the another bus master device.

5. The bus master device of claim 1 wherein said snoop logic block comprises:

a snoop register coupled to the common bus having a priority field which stores said current priority signal, and an increment field which indicates an address of said memory segment;

a memory segment access detect circuit having a first input terminal coupled to the common bus for receiving a bus request data word, a second input terminal coupled to said increment field of said snoop register, and an output terminal for providing a priority change signal, said memory segment access detect circuit providing said priority change signal in a first logic state in response to a portion of said bus request data word equaling said increment field; and

a priority update circuit coupled to said snoop register having a first input terminal for receiving said current priority signal, a second input terminal coupled to said memory segment access detect circuit for receiving said priority change signal, and an output terminal coupled to said priority field of said snoop register for providing an updated priority signal equal to said current priority signal plus a predetermined number if said priority change signal is in said first logic state.

6. The bus master device of claim 5, wherein said snoop logic block further comprises a comparator having a first input terminal for receiving the updated priority signal, a second input terminal for receiving a preprogrammed threshold, and an output terminal for providing a ready signal in response to the updated priority signal comparing favorably with the preprogrammed threshold, wherein the ready signal indicates to the bus master device that a task is ready to be executed.

7. The bus master device of claim 6, wherein the preprogrammed threshold is included within a bit field of said snoop register.

8. The bus master device of claim 5 wherein said snoop register further comprises an increment value field for storing an increment value, and wherein said priority update circuit further has a third input terminal for receiving said increment value, and a second output terminal coupled to said increment value field, wherein said priority update circuit adds a held value increment to said increment value and provides a sum thereof to said second output terminal when said priority change signal is in said first logic state.

9. The bus master device of claim 8 wherein said snoop register further includes an increment pre-scale field which stores said predetermined number.

10. The bus master device of claim 9 wherein said increment pre-scale field also stores a pre-scale value and said priority update circuit further includes a modulo counter having an input terminal coupled to said increment pre-scale field, a control terminal for receiving said priority change signal, and an output terminal coupled to said increment value field of said snoop register, wherein said modulo counter increments said increment value using said pre-scale value as a modulus number.

11. The bus master device of claim 8 wherein:

said snoop register further includes a decrement field which indicates an address of a second memory segment;

said memory segment access detect circuit further has a third input terminal coupled to said decrement field of said snoop register, said memory segment access detect circuit providing said priority change signal in a second logic state in response to said portion of said bus request data word equaling said decrement field; and

said priority update circuit further provides said updated priority signal equal to said current priority signal minus a second predetermined number if said priority change signal is in said second logic state.

12. The bus master device of claim 11 wherein said snoop register further comprises an decrement value field for storing an decrement value, and wherein said priority update circuit further has a fourth input terminal for receiving said decrement value, and a third output terminal coupled to said decrement value field, wherein said priority update circuit adds a held value increment to said decrement value and provides a sum thereof to said third output terminal when said priority change signal is in said second logic state.

13. The bus master device of claim 12 wherein said memory segment access detect circuit comprises:

a first comparator having a first input terminal for receiving said portion of said bus request data word, a second input terminal for receiving said increment value, and an output terminal; and

a second comparator having a first input terminal for receiving said portion of said bus request data word, a second input terminal for receiving said decrement value, and an output terminal,

wherein said memory segment access detect circuit provides said priority change signal in said first logic state in response to said portion of said bus request data word equaling said increment value, and providing said priority change signal in said second logic state in response to said portion of said bus request data word equaling said decrement value.

14. A bus master device for coupling to a shared memory via a common bus, the common bus adapted to couple to at least one other bus master device, comprising:

a snoop register coupled to the common bus having a priority field which stores a current priority signal which indicates a degree of fullness of a memory segment which is located in the shared memory, and an increment field which indicates an address of said memory segment;

a memory segment access detect circuit having a first input terminal coupled to the common bus for receiving a bus request data word, a second input terminal coupled to said increment field of said snoop register, and an output terminal for providing a priority change signal, said memory segment access detect circuit providing said priority change signal in a first logic state in response to a portion of said bus request data word equaling said increment field;

a priority update circuit coupled to said snoop register having a first input terminal for receiving said current priority signal, a second input terminal coupled to said memory segment access detect circuit for receiving said priority change signal, and an output terminal coupled to said priority field of said snoop register for providing an updated priority signal equal to said current priority signal plus a predetermined number if said priority change signal is in said first logic state; and

an execution unit having an input terminal for receiving said current priority signal, and an output terminal coupled to an output terminal of the bus master device for periodically arbitrating for usage of the common bus in response to an internal operation by providing said current priority signal to said output terminal.

15. The bus master device of claim 14 wherein:

said snoop register further includes a decrement field which indicates an address of a second memory segment;

said memory segment access detect circuit further has a third input terminal coupled to said decrement field of said snoop register, said memory segment access detect circuit providing said priority change signal in a second logic state in response to said portion of said bus request data word equaling said decrement field; and

said priority update circuit further provides said updated priority signal equal to said current priority signal minus a second predetermined number if said priority change signal is in said second logic state.

16. The bus master device of claim 15 wherein said snoop register further comprises an increment value field coupled to a fourth input terminal of said priority update circuit which stores an increment value, and a decrement value field coupled to a fifth input terminal of said priority update circuit which stores an decrement value.

17. The bus master device of claim 14 wherein said memory segment access detect circuit comprises:

a first comparator having a first input terminal for receiving said portion of said bus request data word, a second input terminal for receiving said increment field, and an output terminal; and

a second comparator having a first input terminal for receiving said portion of said bus request data word, a second input terminal for receiving said decrement field, and an output terminal,

wherein said memory segment access detect circuit provides said priority signal in said first logic state in response to said portion of said bus request data word equaling said increment field, and providing said priority signal in said second logic state in response to said portion of said bus request data word equaling said decrement field.

18. The bus master device of claim 14, wherein said priority update circuit further comprises a comparator having a first input terminal for receiving the updated priority signal, a second input terminal for receiving a preprogrammed threshold, and an output terminal for providing a ready signal in response to the updated priority signal comparing favorably with the preprogrammed threshold, wherein the ready signal indicates to the bus master device that a task is ready to be executed.

19. The bus master device of claim 18, wherein the preprogrammed threshold is included within a bit field of said snoop register.

20. A data processing system comprising:

a common bus;

a first bus master device having a data terminal coupled to said common bus, and an output terminal for providing a first priority signal indicative of a fullness state of a first memory segment associated therewith, said first bus master device transferring data over said common bus after receiving a first bus grant signal;

a second bus master device having a data terminal coupled to said common bus, and an output terminal for providing a second priority signal indicative of a fullness state of a second memory segment associated therewith, said second bus master device transferring data over said common bus after receiving a second bus grant signal; and

a bus arbiter having a first input terminal for receiving said first priority signal, a second input terminal for receiving said second priority signal, and an output terminal coupled to said common bus for providing a selected one of said first bus grant signal and said second bus grant signal as determined by a relative size of said first priority signal and said second priority signal.

21. The data processing system of claim 20 further comprising a shared memory coupled to said common bus, wherein said first memory segment is stored in a first portion of said shared memory and said second memory segment is stored in a second portion of said shared memory.

22. The data processing system of claim 20 wherein said first memory segment and said second memory segment comprise a common memory segment.

23. The data processing system of claim 22 wherein said first priority signal indicates a number of filled entries of said common memory segment, and wherein said second priority signal indicates a number of empty entries of said common memory segment.

24. The data processing system of claim 20 wherein said first bus master device includes a snoop logic block having an input coupled to said common bus, and an output coupled to said output terminal thereof, said snoop logic block changing a value of said first priority signal in response to said second bus master device accessing said common memory segment.

25. The data processing system of claim 24, wherein said snoop logic block further comprises a comparator having a first input terminal for receiving the changed value of the first priority signal, a second input terminal for receiving a preprogrammed threshold, and an output terminal for providing a ready signal in response to the changed value of the first priority signal comparing favorably with the preprogrammed threshold, wherein the ready signal indicates to the first bus master device that a task is ready to be executed.

26. The data processing system of claim 25, wherein the preprogrammed threshold is included within a bit field of said snoop register.

27. The data processing system of claim 20 wherein said first bus master device and said second bus master device comprise signal processors.

28. The data processing system of claim 20 wherein each of said first bus master device and said second bus master device comprise separate monolithic integrated circuits.

29. A data processing system comprising:

a bus;

a memory unit, coupled to the bus, the memory unit organized as a plurality of memory segments for storing data;

a first execution unit, coupled to the bus, and having an input terminal for receiving a first priority signal which indicates a degree of fullness of a memory segment of the memory unit, said first execution unit for processing a plurality of tasks;

a first logic block having an input terminal coupled to the bus, and an output terminal coupled to said input terminal of said first execution unit for providing said first priority signal thereto, wherein said first logic block monitors a fullness state of said memory segment and changes said first priority signal in response to the fullness state; and

a comparator having a first input terminal coupled to the output terminal of the snoop logic block, a second input terminal for receiving a preprogrammed threshold, and an output terminal for providing a ready signal in response to the first priority signal comparing favorably with the preprogrammed threshold, wherein the ready signal indicates that a task of the plurality of tasks is ready to be processed.

30. The data processing system of claim 29, wherein said first logic block comprises:

a register coupled to the bus having a priority field which stores said first priority signal, and an increment field which indicates an address of said memory segment;

a memory segment access detect circuit having a first input terminal coupled to the bus for receiving a bus request data word, a second input terminal coupled to said increment field of said register, and an output terminal for providing a priority change signal, said memory segment access detect circuit providing said priority change signal in a first logic state in response to a portion of said bus request data word equaling said increment field; and

a priority update circuit coupled to said register having a first input terminal for receiving said first priority signal, a second input terminal coupled to said memory segment access detect circuit for receiving said priority change signal, and an output terminal coupled to said priority field of said snoop register for providing an updated first priority signal equal to said priority signal plus a predetermined number if said priority change signal is in said first logic state.

31. The data processing system of claim 30, wherein the preprogrammed threshold is included within a bit field of said register.

32. The data processing system of claim 29, further comprising:

a second execution unit coupled to the bus, said second execution unit having an input terminal for receiving a second priority signal which indicates, directly or indirectly, a degree of fullness of a memory segment of the memory unit;

a second logic block having an input terminal coupled to the bus, and an output terminal coupled to said input terminal of said second execution unit for providing said second priority signal thereto, wherein said second logic block monitors a fullness state of said memory segment and changes said second priority signal in response to the fullness state; and

a bus arbiter having a first input terminal for receiving said first priority signal, a second input terminal for receiving said second priority signal, and an output terminal coupled to said bus for providing a bus grant signal to either the first execution unit or the second execution unit as determined by a relative size of said first priority signal and said second priority signal.

33. The data processing system of claim 32, wherein said second logic block comprises:

a register coupled to the bus having a priority field which stores said second priority signal, and an increment field which indicates an address of said memory segment;

a memory segment access detect circuit having a first input terminal coupled to the bus for receiving a bus request data word, a second input terminal coupled to said increment field of said register, and an output terminal for providing a priority change signal, said memory segment access detect circuit providing said priority change signal in a first logic state in response to a portion of said bus request data word equaling said increment field; and

a priority update circuit coupled to said register having a first input terminal for receiving said second priority signal, a second input terminal coupled to said memory segment access detect circuit for receiving said priority change signal, and an output terminal coupled to said priority field of said register for providing an updated second priority signal equal to said priority signal plus a predetermined number if said priority change signal is in said first logic state.