Systems, methods and computer readable medium for management of data buffers using functional paradigm

Abstract

A computer-implemented method, data processing system and computer readable medium manages processing of data entries in a data buffer. Data entries are stored in a data buffer. A representation of a two-directional matrix is annotated to mark the data arrivals as a plurality of entries. In addition, the two-directional matrix is annotated to define a valid processing period for the data entries. The data entries in the data buffer are processed by removing the data entries from the data buffer, marked for processing in the two-dimensional matrix during the valid processing period, by annotating the matrix, labeled as A.sub.CS, to define the number of available entries as a cumulative sum along the columns, A-X, such that A.sub.CS=cumsum(A-X), where cumsum is the cumulative column-sum. Finally, the data entries from the data buffer are processed to determine the entries removed from the data buffer as defined by the row-sum of X. The technique has application for implementing a buffer management system for tax loss carry forward calculations.

Claims

1. A computer-implemented method for managing processing of data entries in a data buffer, comprising: storing a plurality of data entries in a data buffer; storing, in computer memory, using at least one processor, a representation of a two-directional matrix, and annotating the two-directional matrix to mark the data arrivals as a plurality of entries in the two-directional matrix such that the entries are arranged in a row direction of the two-directional matrix, based on a time of receipt of the data arrivals, and in a column direction of the two-directional matrix to uniquely identify the data entries; annotating, using a processor unit and the memory, the representation of the two-directional matrix the data entries to define a valid processing period for the data entries; processing the data entries in the data buffer, using the processor unit and the memory, by removing the data entries from the data buffer, marked for processing in the two-dimensional matrix during the valid processing period, by annotating the matrix, labeled as A.sub.CS, to define the number of available entries as a cumulative sum along the columns, A-X: A.sub.CS=cumsum(A-X), where cumsum is the cumulative column-sum; and processing, using the processor unit and the memory, to determine the entries removed from the data buffer as defined by the row-sum of X.

2. The computer-implemented method as set forth in claim 1, wherein the processing of the data arrivals in the data buffer comprises removing entries from the data buffer with a dispatch policy that comprises a first-in-first-out policy.

3. The computer-implemented method as set forth in claim 1, wherein the processing of the data arrivals in the data buffer comprises removing entries from the data buffer with a dispatch policy that comprises a last-in-first-out policy.

4. The computer-implemented method as set forth in claim 1, wherein annotating, using the processor unit and the memory, the two-directional matrix, labeled X, and applying a constraint on the removals of the data entries such that the elementwise product of X*D=X, such that X can only have non-zero values when D is 1.

5. The computer-implemented method as set forth in claim 4, further for annotating, using the processor unit and the memory, the two-directional matrix, labeled as D.sub.MAX, and applying a constraint on the removals that signify that removals of the data entries from the data buffer are limited such that X<=D.sub.MAX constraint.

6. The computer-implemented method as set forth in claim 1, further for specifying a time-expiration on data processing in the valid processing period.

7. The computer-implemented method as set forth in claim 1, further for applying a constraint on A.sub.CS such that a total number of data entries cannot exceed a certain maximum: A.sub.CS<BUFFER_MAX, during the valid processing period.

8. The computer-implemented method as set forth in claim 1, further for applying a constraint on a final column vector of A.sub.CS such that A.sub.CS[:,1]=0 sets the final column vector to zero so as to force all queues to be processed.

9. The computer-implemented method as set forth in claim 1, further comprising: receiving financial data on accounting losses, earnings and tax constraints that define a number of years to apply losses to earnings; and executing the process of claim 1 so as to solve a tax loss carry forward scenario.

10. The computer-implemented method as set forth in claim 1, further comprising: receiving financial data on accounting losses, earnings and tax constraints that define a number of years to apply losses to earnings; and executing the process of claim 1 so as to solve a tax loss carry forward scenario.

11. A computer-readable medium comprising a plurality of instructions, which when executed by a processor unit and memory, manage processing of data entries in a data buffer, computer-readable medium comprising instructions for: storing a plurality of data entries in a data buffer; storing a representation of a two-directional matrix, and annotating the two-directional matrix to mark the data arrivals as a plurality of entries in the two-directional matrix such that the entries are arranged in a row direction of the two-directional matrix, based on a time of receipt of the data arrivals, and in a column direction of the two-directional matrix to uniquely identify the data entries; annotating the representation of the two-directional matrix the data entries to define a valid processing period for the data entries; processing the data entries in the data buffer, using the processor unit and the memory, by removing the data entries from the data buffer, marked for processing in the two-dimensional matrix during the valid processing period, by annotating the matrix, labeled as A.sub.CS, to define the number of available entries as a cumulative sum along the columns, A-X: A.sub.CS=cumsum(A-X), where cumsum is the cumulative column-sum; and processing, using the processor unit and the memory, to determine the entries removed from the data buffer as defined by the row-sum of X.

12. The computer-readable medium as set forth in claim 11, wherein the processing of the data arrivals in the data buffer comprises removing entries from the data buffer with a dispatch policy that comprises a first-in-first-out policy.

13. The computer-readable medium as set forth in claim 11, wherein the processing of the data arrivals in the data buffer comprises removing entries from the data buffer with a dispatch policy that comprises a last-in-first-out policy.

14. The computer-implemented method as set forth in claim 11, wherein annotating the two-directional matrix, labeled X, and applying a constraint on the removals of the data entries such that the elementwise product of X*D=X, such that X can only have non-zero values when D is 1.

15. The computer-readable medium as set forth in claim 14, further for annotating the two-directional matrix, labeled as D.sub.MAX, and applying a constraint on the removals that signify that removals of the data entries from the data buffer are limited such that X<=D.sub.MAX constraint.

16. The computer-readable medium as set forth in claim 11, further for specifying a time-expiration on data processing in the valid processing period.

17. The computer-readable medium as set forth in claim 11, further for applying a constraint on A.sub.CS such that a total number of data entries cannot exceed a certain maximum: A.sub.CS<BUFFER_MAX, during the valid processing period.

18. The computer-readable medium as set forth in claim 11, further for applying a constraint on a final column vector of A.sub.CS such that A.sub.CS[:,1]=0 sets the final column vector to zero so as to force all queues to be processed.

19. A data processing system for managing processing of data entries in a data buffer, comprising: a data buffer for storing a plurality of data entries; a processor unit, comprising at least one processor, and memory to: store a representation of a two-directional matrix, and to annotate the two-directional matrix to mark the data arrivals as a plurality of entries in the two-directional matrix such that the entries are arranged in a row direction of the two-directional matrix, based on a time of receipt of the data arrivals, and in a column direction of the two-directional matrix to uniquely identify the data entries; annotate the representation of the two-directional matrix the data entries to define a valid processing period for the data entries; process the data entries in the data buffer by removing the data entries from the data buffer, marked for processing in the two-dimensional matrix during the valid processing period, to annotate the matrix, labeled as A.sub.CS, to define the number of available entries as a cumulative sum along the columns, A-X: A.sub.CS=cumsum(A-X), where cumsum is the cumulative column-sum; and process to determine the entries removed from the data buffer as defined by the row-sum of X.

20. The data processing system as set forth in claim 19, wherein to annotate the two-directional matrix, labeled X comprises to apply a constraint on the removals of the data entries such that the elementwise product of X*D=X, such that X can only have non-zero values when D is 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a block diagram of a data processing system exemplary to implement embodiments disclosed herein.

(2) FIG. 2 illustrates a two-dimensional matrix for a representation of example data arrivals.

(3) FIG. 3 depicts a two-dimensional matrix used to annotate data entries.

(4) FIG. 4 illustrates a matrix X that defines the removals from the queue.

(5) FIG. 5 illustrates an example two-dimensional matrix configured in accordance with some embodiments.

(6) FIG. 6 illustrates removal of example data entries from the rows of the two-dimensional matrix.

(7) FIG. 7 illustrates a flow sequence for processing data entries in accordance with some embodiments.

(8) FIG. 8 illustrates a withdrawal matrix, D, that defines the valid periods to offset revenue with losses.

(9) FIG. 9 illustrates an example diagonal matrix, A, filled with arrivals in the queue.

(10) FIG. 10 illustrates an example matrix, X, as the variable matrix defining the withdrawal amount from the cash flow streams.

(11) FIG. 11 illustrates an example matrix, A.sub.CS, that defines the available funds in each stream.

(12) FIG. 12 illustrates an example matrix as the row-sum of matrix X.

(13) FIG. 13 depicts a diagrammatic representation of a machine in the exemplary form of a computer system within which a set of instructions for causing the machine to perform any one of the methodologies discussed above may be executed.

DETAILED DESCRIPTION

(14) FIG. 1 is a block diagram of a data processing system exemplary to implement embodiments disclosed herein. In its simplest form, data processing system 100 receives data (data arrivals) at input/output (I/O) peripherals 150, stores data arrivals in memory (114) or storage (102), processes data entries via processor unit (140), and potentially outputs data through one or more I/O peripherals 150. Processor unit 140 may be configured to include one or more processors (i.e., a single or multi processor system). As shown in FIG. 1, processor unit 140 uses bus 130 to execute protocols and transfer data among storage 102/memory 114, as well as I/O peripherals 150. Preferably, storage 102 represents permanent memory, such as a hard drive or flash drives, typically used in computer systems to store data without power requirements. Memory (114) represents a broad class of media, such as high-speed DRAM, used to store data during active data processing.

(15) For the exemplary embodiments disclosed in FIG. 1, storage 102 stores one or more application programs (e.g., stores n programs), labeled application.sub.1 (104), application (106) and application.sub.n (108). As is well understood, application programs (software), run on the data processing system (100) to provide functionality to the user. For example, application.sub.1 (104) may represent a spreadsheet program or a complex scheduling program. In one embodiment, one of the application programs (104, 106 or 108) comprises a tax management program that solves complex tax loss carry forward problems. Further details regarding an embodiment for an application program that solves tax loss carry forward problems is described more fully below.

(16) The data processing system (100) further includes operating system (112), located in storage (102). Operating system 112 is intended to represent a broad class of utility software necessary to run the operations of a computer, such as data processing system (100). Storage (102) also stores functional paradigm modules (110). In general, functional paradigm modules (110) run on data processing system (100) to implement the embodiments of managing data buffers using a functional paradigm, as described herein.

(17) For the exemplary embodiments shown in FIG. 1, memory (114) stores operating system (116), to represent that at least a portion of the operating system is loaded into active memory. The functional paradigm modules (110), loaded into memory (114), dispatch policy manager (118) and constraint manager (120). Similarly, also depicted as resident in memory (114), is one or more active applications, such as application program (122), shown as application.sub.1. Furthermore, the exemplary embodiment of memory (114) includes a two dimensional matrix (126) and data buffers (124). Data buffers (124) store data entries received, by way of example, I/O peripherals 150 awaiting processing by the processor unit 140. In general, and as described more fully below, the dispatch policy manager (118) and constraint manager (120) receive parameters from application 122, and, in turn, implement/schedule processing of data entries in data buffers (124), using two-dimensional matrix (126), in accordance with the constraints imposed by application (122).

(18) Data arrivals are represented as information queues in a matrix, corresponding to the time in which the data arrived. FIG. 2 illustrates a two-dimensional matrix for a representation of example data arrivals. For this example, in (d2, T2), 20 data units arrived in the time period T2 and is named as d2.

(19) The process then arranges the data to define the valid processing periods. FIG. 3 depicts a two-dimensional matrix used to annotate data entries. Specifically, FIG. 3 illustrates the data entries in the shaded boxes of matrix D. Values of 1 indicate that a data entry in the queue may be processed (i.e., the data entry is valid in the processing period). The D matrix may also be formed from a D.sub.MAX matrix, which specifies maximum withdrawals in that period. Non-zero D.sub.MAX values are is in D. In other embodiments, D is banded, and a time-expiration is placed on data processing. If D is upper triangular with all 1s, queues will be allowed to accumulate indefinitely.

(20) FIG. 4 illustrates a matrix X that defines the removals from the queue. Specifically, matrix X, shown in FIG. 4, is the variable matrix defining the removals from the queue such that X>=0. Thus, withdrawals must be positive in X. In some embodiments, a constraint is applied such that the elementwise product of X*D=X, such that elements of X can only be non-zero where elements in D are 1. This is a linear constraint.

(21) Where a D.sub.MAX matrix is used, we apply a X<=D.sub.MAX constraint, meaning removals from a queue are limited.

(22) Matrix A.sub.CS defines the number of available data items in each queue stream as the cumulative sum along columns of A-X:

(23) A.sub.CS=cumsum(A-X), where cumsum is the cumulative column-sum

(24) FIG. 5 illustrates an example two-dimensional matrix configured in accordance with some embodiments. The quantity A-X, shown in FIG. 5, illustrates inspection of the first few fields. The direction of the cumulative sum is indicated by the arrow.

(25) For this example, the constraints are:

(26) Row 1:
0x.sub.1,1>=0,
0x.sub.1,2x.sub.1,1>=0,
0x.sub.1,3x.sub.1,2x.sub.1,1>=0

(27) Row 2:
20x.sub.2,2>=0,
20x.sub.2,3x.sub.2,2>=0,
20x.sub.2,4x.sub.2,3x.sub.2,2>=0,

(28) However, as the problem is represented in matrix notation, the expression may be written: A.sub.CS>=0. That constraint simply states that data must exist in the queue in order to remove it.

(29) Constraints on A.sub.CS may be placed such that the total buffer cannot exceed a certain maximum: A.sub.CS<BUFFER_MAX. This is relevant in storage/memory limited applications.

(30) Constraints may also be placed on the final column vector of A.sub.CS, with the notation A.sub.CS[:,1]. Setting that final column vector to zero forces all queues to be processed:

(31) A.sub.CS[:,1]==0

(32) Finally, piecing together our objective, a measure of the total data items removed from all queues is determined. To this end, CONSUMED_ITEMS is defined as the row-sum of X. FIG. 6 illustrates removal of example data entries from the rows of the two-dimensional matrix.

(33) FIG. 7 illustrates a flow sequence for processing data entries in accordance with some embodiments. The process generates a representation of a two-dimensional matrix, for storage in memory, of the data entries (FIG. 7, 100). Based on the application (e.g., parameters received from the application program), the process defines linear constraints by defining constraints in the matrix D, such as D.sub.MAX (FIG. 7, 200). The process defines a valid processing period in the matrix (FIG. 7, 300). Next, by annotating the matrix, the process defines removals from the queue (FIG. 7, 400). Rules, which define priority to process the data entries in the queue, include, but are not limited to: applying linear constraints; applying constraints around a maximum storage limitations (i.e., storage limitation constraints), and applying minimum and maximum withdrawal constraints (FIGS. 7, 500, 600 and 700).

(34) The embodiments disclosed herein are broadly applicable to queue management problems. Some applications includes Tax Loss Carry Forward scenarios, and trading of stock for tax optimization.

(35) The embodiments disclosed herein include a real-time data management control system.

(36) The embodiments disclosed herein further include in a real-time data management control system, where forecasts about future buffers influence immediate actions.

(37) Application for the Embodiments in Data Buffers Management:

(38) To achieve a FIFO objective, data entries should come out of the queue as quickly as possible. This may be represented by taking the sum of the cumulative sum of the items processed in each time interval. The sum of the cumulative sum will be larger when items are processed earlier, thus we seek to maximize this value.

(39) Maximize sum(cumsum(CONSUMED_ITEMS))

(40) To achieve a LIFO objective, older entries are managed to reside in the queue for as long as possible. This may be represented by minimizing the sum of the cumulative sum of the items processed in each interval as the sum of the cumulative sum will be smaller when processing is deferred.

(41) Minimize sum(cumsum(CONSUMED_ITEMS))

(42) Application of Computer-Implemented Technique for Calculation of Tax Carry Forward

(43) Tax Loss Carry Forward policies differ widely from country to country. In Tax Loss Carry Forward, past accounting losses can be used to offset taxes on future earnings. In most instances, the ability for past losses to offset future earnings is limited to a certain number of years. For example, if losses can be carried forward for 5 years, losses in Year 1 can be offset until Year 5, and losses in Year 2 can be offset until Year 6. This creates a number of loss streams, each of which needs to be tracked across every year.

(44) Traditional implementations use a combination of IF-ELSE statements or other esoteric functions such as Microsoft Excel's OFFSET, which is notoriously difficult to use and error-prone. Further, every subtle rule change requires a new implementation or review of the calculations.

(45) The methods below describe embodiments for software to perform these calculations.

(46) From a Discount Cash Flow Model, Earnings Before Taxes (EBT) Profits (EBTP) and Losses (EBTL) are separated into two vectors. EBT=EBTPEBTL. Zeros fill losses in the EBTP and zeros fill profits in EBTL. Mapping this to the embodiments described above, losses are treated as arrivals in the queue, as shown below in TABLE 1.

(47) TABLE-US-00001 TABLE 1 Variable Y1 Y2 Y3 Y4 Y5 Y6 Y7 . . . Earnings Before Taxes 10 20 4 15 1 2 30 . . . Earnings Before 10 0 4 15 0 2 30 . . . Taxes, Profits (EBTP) Earnings Before 0 20 0 0 1 0 0 . . . Taxes, Losses (EBTL)

(48) A withdrawal matrix, D, defines the valid periods to offset revenue with losses, as shown in FIG. 8. Here, the number of periods is three years and as such each row contains three elements with value of 1 with the rest zeros. This matrix is upper triangular. Rows represent distinct cash flow streams and columns represent when additions or withdrawals can be made into those streams. This is country-specific and may take on the form of a banded-matrix (carry forward limited to N years), upper-triangular (unlimited carry forward), or any other form.

(49) Diagonal matrix A, shown in FIG. 9, is filled with EBTL (arrival in queues). Matrix X, shown in FIG. 10, is the variable matrix defining the withdrawal amount from the cash flow streams. X>=0 (defines withdrawals to be positive in X). A constraint is applied such that the elementwise product of X*D=X, such that X can only have non-zero values when D is 1. This is a linear constraint.

(50) Matrix A.sub.CS, shown in FIG. 11, defines the available funds in each stream as the cumulative sum along columns of A-X:

(51) A.sub.CS=cumsum(A-X), where cumsum is the cumulative column-sum

(52) The quantity A-X is shown in FIG. 11 for inspection of the first few fields. The direction of the cumulative sum is indicated by the arrow shown in FIG. 11.

(53) For this example problem, we would set up these constraints:

(54) Row 1:
0x.sub.1,1>=0,
0x.sub.1,2x.sub.1,1>=0,
0x.sub.1,3x.sub.1,2x.sub.1,1>=0

(55) Row 2:
20x.sub.2,2>=0,
20x.sub.2,3x.sub.2,2>=0,
20x.sub.2,4x.sub.2,3x.sub.2,2>=0,

(56) However, as the problem is represented in matrix notation, it may be expressed as: A.sub.CS>=0. That constraint simply states that money must be available in each stream in order to withdraw.

(57) Finally, piecing together our objective, a measure of earnings is sought. CONSUMED_LOSSES is defined to offset accounting profits as the row-sum of X as shown in FIG. 12.

(58) CONSUMED_LOSSES can also be limited using a constraint that will cap the amount of revenue that can be offset by losses, LOSS_MAX: CONSUMED_LOSSES<=LOSS_MAX.

(59) Net taxable earnings are the earnings profits before taxes (EBTP) minus these consumed losses: NET_TAXABLE_EARNINGS=EBTPCONSUMED_LOSSES

(60) The objective is to minimize the net taxable earnings. As earnings occur over multiple years, this is compressed to a scalar. NPV may be used to express a preference for tax optimization in early years. The behavior of the model is not particularly sensitive to the choice of this penalty function.

(61) Objective: Minimize NPV(NET_TAXABLE_EARNINGS). The NPV function also requires a discount rate, but is not shown here.

(62) In this example, a First-In First-Out (FIFO) policy is achieved, although this is a result of the optimization rather than being explicitly enforced.

(63) The innovation disclosed herein provides for a data buffer management scheme that explicitly satisfies the objectives. The innovation disclosed herein further provides for implementing a buffer management system as a convex optimization with linear constraints using linear or convex objectives. The use of optimization permits use of a functional programmatic interface to the algorithm, rather than an imperative one. The innovation disclosed herein further provides for implementing a buffer management system for tax loss carry forward calculations.

(64) The inventions disclosed analyze the buffer management problem as a constraint based optimization, and rely on highly-efficient algorithms to determine feasibility and a solution. The constraint-based optimization provides for a testable framework for calculating sub-problems from the parent solution. Sub-problems from the parent solution are formed by the addition of constraints and customization of objectives. These input mechanisms, expressed in matrix notation, are easy to understand and can be visualized for review.

(65) Additional System Architecture Examples

(66) FIG. 13 depicts a diagrammatic representation of a machine in the exemplary form of a computer system 10A00 within which a set of instructions for causing the machine to perform any one of the methodologies discussed above may be executed. In alternative embodiments, the machine may comprise a network router, a network switch, a network bridge, a personal digital assistant (PDA), a cellular telephone, a web appliance, or any machine capable of executing a sequence of instructions that specify actions to be taken by that machine.

(67) The computer system 10A00 includes a CPU partition having one or more processors (e.g., processor 1002.sub.1, processor 1002.sub.2, etc.), a main memory comprising one or more main memory segments (e.g., main memory segment 1004.sub.1, main memory segment 1004.sub.2, etc.), and one or more static memories (e.g., static memory 1006.sub.1, static memory 1006.sub.2, etc.), any of which components communicate with each other via a bus 1008. The computer system 10A00 may further include one or more video display units (e.g., display unit 1010.sub.1, display unit 1010.sub.2, etc.) such as an LED display, or a liquid crystal display (LCD), a cathode ray tube (CRT), etc. The computer system 10A00 can also include one or more input devices (e.g., input device 1012.sub.1, input device 1012.sub.2, alphanumeric input device, keyboard, pointing device, mouse, etc.), one or more database interfaces (e.g., database interface 1014.sub.1, database interface 1014.sub.2, etc.), one or more disk drive units (e.g., drive unit 1016.sub.1, drive unit 1016.sub.2, etc.), one or more signal generation devices (e.g., signal generation device 1018.sub.1, signal generation device 1018.sub.2, etc.), and one or more network interface devices (e.g., network interface device 1020.sub.1, network interface device 1020.sub.2, etc.).

(68) The disk drive units can include one or more instances of a machine-readable medium 1024 on which is stored one or more instances of a data table 1019 to store electronic information records. The machine-readable medium 1024 can further store a set of instructions 1026.sub.0 (e.g., software) embodying any one, or all, of the methodologies described above. A set of instructions 1026.sub.1 can also be stored within the main memory (e.g., in main memory segment 1004.sub.1). Further, a set of instructions 1026.sub.2 can also be stored within the one or more processors (e.g., processor 1002.sub.1). Such instructions and/or electronic information may further be transmitted or received via the network interface devices at one or more network interface ports (e.g., network interface port 1023.sub.1, network interface port 1023.sub.2, etc.). Specifically, the network interface devices can communicate electronic information across a network using one or more optical links, Ethernet links, wireline links, wireless links, and/or other electronic communication links (e.g., communication link 1022.sub.1, communication link 1022.sub.2, etc.). One or more network protocol packets (e.g., network protocol packet 1021.sub.1, network protocol packet 1021.sub.2, etc.) can be used to hold the electronic information (e.g., electronic data records) for transmission across an electronic communications network (e.g., network 1048). In some embodiments, the network 1048 may include, without limitation, the web (i.e., the Internet), one or more local area networks (LANs), one or more wide area networks (WANs), one or more wireless networks, and/or one or more cellular networks.

(69) The computer system 10A00 can be used to implement a client system and/or a server system, and/or any portion of network infrastructure.

(70) It is to be understood that various embodiments may be used as, or to support, software programs executed upon some form of processing core (such as the CPU of a computer) or otherwise implemented or realized upon or within a machine or computer readable medium. A machine-readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium includes read-only memory (ROM), random access memory (RAM), magnetic disk storage media, optical storage media, flash memory devices, or any other type of non-transitory media suitable for storing or transmitting information.

(71) A module as used herein can be implemented using any mix of any portions of the system memory, and any extent of hard-wired circuitry including hard-wired circuitry embodied as one or more processors (e.g., processor 1002.sub.1, processor 1002.sub.2, etc.).