System for estimating worst time duration required to execute procedure calls and looking ahead/preparing for the next stack operation of the forthcoming procedure calls

• US 5,832,289 A
• Filed: 01/10/1997
• Issued: 11/03/1998
• Est. Priority Date: 09/20/1991
• Status: Expired due to Term

• Current Assignee: Steven M Shaw, Venson M. Shaw
• Original Assignee: Steven M Shaw, Venson M. Shaw
• Inventors: Shaw, Venson M., Shaw, Steven M.
• Primary Examiner(s): AN, MENG AI T
• Application Number:
  US08/781,213
• Time in Patent Office: 662 Days
• Field of Search: 395/200.31, 395/200.33, 395/800.3, 395/559, 395/614, 395/615, 395/672, 395/878, 395/572
• US Class Current: 712/30
• CPC Class Codes: G06F 9/465 Distributed object oriented systems remote method invocation [RMI] G06F9/548
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: H04L 69/32 Architecture of open systems interconnection [OSI] 7-layer type protocol stacks, e.g. the interfaces between the data link level and the physical level
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04N 1/00204 with a digital computer or a digital computer system, e.g. an internet server programmed control between transmitter and receiver or between image input and image output device H04N1/32561
• CPC Class Codes: H04N 1/00392 Other manual input means, e.g. digitisers or writing tablets
• CPC Class Codes: H04N 1/32502 in systems having a plurality of input or output devices
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding
• CPC Class Codes: H04N 21/426 Internal components of the client ; Characteristics thereof H04N5/44 takes precedence
• CPC Class Codes: H04N 2201/0081 Image reader H04N2201/0091 - H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/0082 Image hardcopy reproducer H04N2201/0091 - H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/0084 Digital still camera
• CPC Class Codes: H04N 2201/0086 Image transceiver H04N2201/0093 and H04N2201/0094 take precedence
• CPC Class Codes: H04N 2201/0087 Image storage device
• CPC Class Codes: H04N 2201/0089 Image display device

Abstract

An improved system utility using pointers and stacks and a method for high level language procedure for representing, storing, retrieving, processing, and/or manipulating documents, said system utilities facilitates compilation, linkage, processing, and management of said high level language procedures. Call, return, and auxiliary stacks are included to store pointers of normal, exceptional/conditional, and alternative operations. A bit mapping logic and smart object memory are used to look ahead, monitor, and predict forthcoming exceptional/conditional operation, a system look-up table further prefetch relevant procedural and data pointers for maintaining pipeline coherence.

Claims

1. An improved system utility, using pointers and stacks for representing document as a high level procedure, and processing said document according to sequential or parallel manipulation of said procedure, said system comprising:

input means for receiving external documents, said input means converting said document to selective internal format;

organizer means for selecting an appropriate hierarchy of logical orders for each of said documents, wherein said hierarchy of logical order can be chapter, section, and paragraphs;

said organizer means further partitioning each of said documents into a plurality of logical partitions according to said selected hierarchy of logical orders;

procedure means, coupled to said organizer means, for producing a hierarchical procedure framework for each of said documents, wherein a logical partition corresponds with document content of a particular logical order, and a companion procedure is assigned to each of said logical partition;

wherein manipulation of said document is performed through executing of said hierarchical procedures framework;

procedure pointer means for assigning a pair of entry and exit pointers for each of said hierarchical procedures framework, said entry and exit pointers provide entry and exit address locations for the document content for each of said logical partition;

procedure stack means for establishing a hierarchical order according to said selected logical order, wherein higher hierarchy represents broader logical order, lower hierarchies represent more detailed logical order;

said procedure stack means further comprising selective plurality of operators, wherein a push operator move from higher to lower hierarchy, a pop operator move from lower to higher hierarchy;

evaluation stack means for representing sequential steps of evaluation, processing, and/or manipulation of each of said logical partitions in the stacks;

interface means for selecting subject of interest from user or application;

search engine means for comparing, correlating, or interpreting said subject of interest with concept, theme, keyword, or topic of document content of each said logical partition, provided said search engine means identify selective plurality of logical partitions with corresponding document contents relevant to said subject of interest; and

browsing means for selectively choosing from plurality of said entry and exit pointers of the procedure pointers means and organizing the pointers in a sequential order;

said browsing means further allowing user or application to review selective document content or a particular subject of interest from one logical partition to another according to said sequential order of the pointers.

2. An improved system utility in accordance with claim 1, using pointers and stacks for representing subject of interest from a selective plurality of users or applications, wherein selecting subjects of interest by founding relevant document content, and referring said subject of interest as a procedure scope for the corresponding logical partition, said system comprising:

input means for receiving a list of subject of interest from the selective plurality of users or applications;

search engine means for comparing, correlating, and/or interpreting said list of subject of interest with concept, theme, keyword, or topic of document content of each of said logical partitions, provided said search engine means identifying selective plurality of logical partitions with corresponding document contents relevant to said subject of interest;

scoping means for creating a procedure scope for each corresponding procedure of said logical partition, said procedure scope comprises a selective plurality of local variables, global variables, and parameters;

(i) each of said local variables representing an individual subject of interest for a particular user or application which have found relevancy within document content of said logical partition;

(ii) each of said global variables representing a common subject of interest for a selective plurality of said users or application which have found relevancy within document content of said document partition;

(iii) each of said parameters representing procedure pointers to select one or plurality of remaining logical partitions which contain the same subject of interest; and

activation means for continuously maintaining a record of currently active user/application and said active user/application'"'"'s subject of interests;

said active means further continuously updating scope for each of said companion procedure assigned to the logical partition, wherein local/global variable and parameter within said scope can be updated according to subject of interest for those currently active user/application.

3. An improved system utility in accordance with claim 1, using pointers and stacks for prediction and flow control of forthcoming sequence of normal and exceptional run time execution of said procedure, in order to manipulate selective logical partitions with document content relevant to subject of interest for a selective one or plurality of active user or application, comprising:

predictor means for looking ahead of execution and determining whether forthcoming execution is a normal operation or an exceptional operation;

(i) normal operation occurs most of the time, wherein the system continue browsing and reviewing document content within the same logical partition, and continue executing next instruction within same procedure;

(ii) exceptional/abnormal operation occurs occasionally, wherein the system complete browsing the document content within the same logical partition, and requiring to enter to a next logical partition or return to a selective one of plurality of previous logical partitions;

wherein the system will need to enter to a next procedure or return to a selective one of plurality of the previous procedure in order to continue execution;

look-ahead address pointer preparation means connected to said prediction means for preparing address pointers for said forthcoming exceptional/abnormal operation in order to maintain continuous execution;

(i) call stack means comprising a list of address pointers for next instruction under normal operation, wherein address preparation is not required since document will continue to be browsed or reviewed unit by unit wherein next address pointer is achieved by incrementing one unit from a current address location;

(ii) return stack means comprising a list of address pointer for next instruction under abnormal/exception operation, wherein address preparation is required since document will not continue to be browsed in the same logical partition;

wherein the address pointer for the next instruction can not be simply achieved by incrementing one unit from a current address location, unless forthcoming pointer can be identified prior to said forthcoming pointer execution time, and execution will be halted until address preparation is performed;

comparator means for continuously comparing a current address location with the address pointer representing end of document content for said logical partition, wherein a significant difference shows next operation is a normal operation, and is approaching end of logical partition, wherein the exceptional operation will arise and address preparation is required;

look-ahead parameter pointer preparation means for looking-up, evaluating, and determining a parameter or another address pointer for a next logical partition which contains document content with the same subject of interest;

return stack preparation means, connected to said look-ahead address pointer preparation means for continuously looking ahead and identifying forthcoming operations require entrance to a next or a previous logical partition, and preparing or assembling a list of address pointer in said return stack, in preparation for said forthcoming operations; and

incrementor means for continuously incrementing current address pointer by one unit and use the address pointer as the address pointer for a next normal operation, said incremetor means further storing said next address pointers in said call stack for facilitating continuous execution.

4. An improved system utility in accordance with claim 1, using pointers and stacks for direct execution of hierarchical high level language procedures in order to manipulate selective logical partitions with document content relevant to the subject of interest for a selective one or plurality of active users or applications, comprising:

operation means for preparing a program sequence for each evaluation, manipulation, and processing operation of the document content of each of the logical partitions;

system look up table (SLUT) means for providing a program storage for all of said program sequence for evaluation, manipulation, and processing operation of the document content of each of the logical partitions;

pointer preparation means for producing an address pointer, including index, attribute, identifier, or descriptor, for referring to each of said evaluation, processing, or manipulation operation of the document content of each of the logical partitions;

stack preparation means connected to said pointer preparation means for providing program control stack and data stack framework for run time execution of said each logical partition;

said stack preparation means preparing said pointers according to run time execution order of evaluation, manipulation, and processing of said document content;

procedure preparation means for producing the hierarchical procedure framework for each document, wherein each of said hierarchical procedure framework enclosing said program control stack and said data stack for evaluation, manipulation, and processing of said document content of said each logical partition; and

run-time direct execution means for executing each of said logical partition within a document according to said program control stack and said data stack;

said run-time direct execution means further referring to said address pointer for each step of evaluation, processing, or manipulation, and directly fetching the program sequence stored within said system look-up-table.

5. An improved system utility in accordance with claim 1, using pointers and stacks for prediction of change of run time environment including active user or application, continuously executing subject of interest, and processing selective logical partitions within a document containing said subject of interest, said system comprising:

environment bit map means for storing status of a run time environment in a one dimensional array of bit map stack, wherein said run time environment provides a current updated list of active user, application, and/or communication bandwidth;

environment bit map stack means for sensitizing change of said run time environment including user, application, and/or communication bandwidth, said environment bit map stack means continuously registering and storing a present run time environment status at top of said one dimensional bit map stack;

said environment bit map stack means further pushing previous run time environment status into a next lower level of said bit map stack, comparing and determining any difference between content stored at top of said bit map stack and content stored at lower level of said bit map stack;

subject bit map means connected to said environment bit map stack means for representing and updating a list of subject of interest of currently active users and applications in a two dimensional array of bit map stack,

subject bit map stack means connected to said subject bit map means for continuously updating the list of subject of interest, and storing current list of subject of interest at top of said two dimensional array bit map stack;

said subject bit map stack means further comparing said current list with previous list for identifying a list of new subject of interest, which is caused by change of active user or application;

prediction means connected to said subject bit map stack means for collecting said list of new subject of interest, and proceeding with evaluation and identification of the selective logical partitions with content relevant to said subject of interest;

procedure frame means connected to said prediction means for preparing a procedure framework for forthcoming run time execution;

(i) object stack means for selecting global variables, local variables, and parameters for each of said logical partition, wherein said global variable representing common interest, and said local variable representing individual interest,

(ii) evaluation stack for selecting sequential computation or evaluation steps required for each of said logical partition;

procedure stack means connected to said procedure frame means for producing a sequence of browsing operation for reviewing the selective logical partitions containing relevant subject of interest;

exception handling means connected to said procedure stack means and said evaluation stack means for identifying exception/abnormal operations which requires an exit from current procedure and an entrance to another procedure; and

return stack means connected to said exception handling means for looking ahead, and preparing a list of address pointers for the forthcoming procedure entry locations;

said return stack means further connected to said evaluation stack for monitoring the evaluation steps when current procedure approaching end of operation, and having a next procedure entry pointer ready at top of said return stack means;

wherein system continue with next procedure without further delay for address preparation.

6. An improved data processor system for executing hierarchical procedure calls, which efficiently compiles, links, processes, and manages a single or plurality of hierarchy high level language procedure calls using evaluation and manipulation of pointers and stacks, said system comprising:

first means for operating in a formatting processor, wherein said first means partitions an application/program specification into a single or plurality hierarchy of independent executable modules;

said first means further including an operating means that partitions each of said modules into single or plurality of executable sub-modules;

second means for operating in a smart object memory, wherein said second means produces a corresponding call pointer data structure for each of said modules or said sub-modules;

said call pointer data structure comprising a procedure call stack and operand call stack;

said procedure call stack including a sequence of next procedure pointer address which correspond with next normal or regular execution steps for each of said modules;

said operand call stack including a sequence of next data pointer address which correspond with local variable scope for each of said modules;

third means for operating in said smart object memory, wherein said third means produces a corresponding return pointer data structure for each of said modules or said sub-modules;

said return pointer data structure including a procedure return stack and operand return stack;

said procedure return stack comprising a sequence of previous or alternative procedure pointer address which correspond with conditional or exceptional execution steps for each of said modules;

said operand return stack comprising a sequence of previous or alternative data pointers which;

fourth means for operating in said smart object memory, wherein said fourth means produces a corresponding auxiliary pointer data structure for each of said modules or said sub-modules;

said auxiliary pointer data structure comprising a single or plurality of auxiliary procedure stacks and a single or plurality of auxiliary operand stacks;

said auxiliary procedure stack including a plurality sequence of previous or subsequent procedure pointer;

said auxiliary operand stack comprising a plurality sequence of next, previous or alternative data pointers which correspond with the local variables scope for call destination modules; and

fifth means for operating in said smart object memory, wherein said fifth means produces a corresponding bit mapping logic for monitoring execution of each of said modules or said sub-modules;

said bit mapping logic determining an appropriate set of procedure pointer and data pointer for maintaining pipeline coherence.

7. An improved data processor system in accordance with claim 6, said bit mapping logic in said fifth means comprising means for predicting/foreseeing, which looking-ahead and monitoring whether forthcoming exceptional or conditional steps are arriving, or changing of activation record is required;

wherein when said means for predicting/foreseeing determines that the forthcoming exceptional or conditional steps are arriving and changing of record is required, said bit mapping logic then prefetching procedural and/or data pointers for maintaining pipeline coherence.

8. An improved data processor system in accordance with claim 6, further providing the pointers and stacks as in software data structure, comprising:

storage means having a memory array or a register array function as stack;

means for allocating a selective plurality of locations in said stack of said storage means, wherein each of said locations represents a level of said stack, and corresponding pointer information for each level of said stack is stored in each of said storage location;

means for assigning one of said storage locations as top of said stack;

indexing means for providing a push or a pop operation for said stack, wherein a push operation is performed by decrementing said storage address by one unit from said storage location representing said top of said stack;

a pop operation is performed by incrementing said storage address by one unit from said storage location representing said top of said stack;

means for writing pointer information into said storage locations for said stack;

means for reading pointer information from said storage locations for said stack; and

means for detecting overflow or underflow of the pointer information in said stack.

9. An improved data processor system in accordance with claim 8, wherein said storage means is not only suitable for the memory array or the register array data structure, it can further be extended to file or database.

10. An improved data processor system in accordance with claim 8, further providing the pointers and stacks for remote execution of said high level language procedure calls, said system comprising:

a server or a host system means, where a plurality of applications are stored as the high level language procedures;

said server means provides pointers and stacks data structure for facilitating run-time execution of said high level language procedures;

a plurality of users or client terminal means;

a networking means for connecting said server and said client terminal means;

means for receiving for the applications from said client terminal means;

scheduler means for determining a selective set of procedures in said application to be performed on said client terminal means, and wherein remaining portion of said application is to be performed at said server;

said scheduler means further preparing corresponding stacks and pointers data structure for said selected set of procedures;

memory map means for communicating/exchanging data, pointer, and/or stack information between said server and said client terminal means, wherein said memory map means selects memory locations on said client terminal means, and maps said memory locations to address space of said server;

means for forwarding the corresponding pointers and stacks information for said selected procedures to said client terminal means;

means in said client for interpreting and performing run-time execution of said selected procedures according to said corresponding pointers and stacks;

means for forwarding result, argument, or parameters of said selected procedures to said server after completion of said run-time execution.

11. An improved data processor system in accordance with claim 10, further providing pointers and stacks for facilitating a downloadable operating system program, said system comprising:

means in said client for performing microkernel system functions;

means in said client for defining a set of selective hardware and/or software system resources information required to be managed by said client;

means for communicating said software system resources information to a server;

means in said server for providing the operating system programs for said client as in a set of high level language based procedures;

said means producing corresponding pointer and stack for facilitating run-time execution of said operating system program;

means for downloading or transporting said pointer and/or stack data structure through said communication means to said client; and

means in said client means for performing run-time execution of said operating system program according to said corresponding pointers and stacks.

12. An improved data processor system in accordance with claim 11, further providing pointers and stacks for facilitating a downloadable operating system program, further comprising:

reconfiguration means for updating change of run-time system resources for said clients;

said reconfiguration means communicating to said server and preparing a second set of pointer and stack data structure for run-time execution of corresponding operating system program, and performing a system reset and downloading said operating system program to said client for continuing the run-time execution of said operating system program.

13. An improved data processor system in accordance with claim 11, further providing pointers and stacks for facilitating a downloadable operating system program, wherein said microkernel system function further comprising:

time critical system functions including execution and scheduling for a multiplicity of threads, synchronization for a multiplicity of processes, and translation and mapping for high level system objects.

14. An improved data processor system in accordance with claim 10, further providing pointers and stacks for facilitating a downloadable communication protocol program, said system comprising:

a single or plurality of communications means, wherein each of said communication means defines a multiple layered of communications protocol program;

a network of client means, wherein each of said client means comprises means for selecting one of said plurality of communications means;

means for representing each of said communications protocol programs in said one of said communications means as a set of high level language procedures, said means for representing further providing the pointers and stacks for facilitating run-time execution of each of said communications protocol programs;

means for constructing a protocol stack, wherein each level of said stack corresponding to a particular layer of said communications protocol, and each level of said stack stores a pointer directing to the corresponding high level language procedures;

means for downloading or transporting said pointers and stack information to said client means;

means in said client means for performing run-time execution of said communications protocol program according to said corresponding pointers and stacks information; and

means in said user for executing said communications protocols for transmitting and/or receiving program or data information.

15. An improved data processor system in accordance with claim 6, further providing time management for the pointers and stacks, said system comprising:

time measurement means for estimating worst case time duration required for executing an entire or a selective portion of the high level language procedure calls;

top of stack means connected to said time measurement means for estimating worst case time duration required for executing remainder portion of a corresponding procedure as referenced by a pointer stored in said top of said stack;

means for looking ahead and preparing next stack operation when approaching end of said worst case time duration, wherein execution of said high level language procedure call is close to finishing;

scheduler means for looking ahead and preparing for terminating present high level language procedure calls, and setting up forthcoming high level language procedure calls;

said scheduler means further examining said forthcoming high level language procedure calls and estimating said worst case time duration required to finish said forthcoming high level language procedure calls.

16. An improved data processor system for executing hierarchical high level language procedure calls, which efficiently compiles, links, processes, and manages a single or plurality of hierarchy high level language procedure calls, using pointers and stacks to represent run-time execution of the high level procedure calls by evaluating and manipulating said pointers and stacks, said system comprising:

means for producing said high level language procedure calls for external documents received;

stack means for storing the run-time execution of said high level language procedure calls;

time measurement means for estimating worst case time duration required for executing an entire or a selective portion of said high level procedure calls;

top of stack means connected to said time measurement means for estimating worst case time duration required for executing remainder portion of a corresponding procedure as referenced by a pointer stored in said top of said stack;

means for looking ahead and preparing next stack operation when approaching end of said worst case time duration, wherein execution of said high level language procedure call is close to finishing; and

scheduler means for looking ahead and preparing for terminating present high level language procedure calls, and setting up forthcoming high level language procedure calls;

said scheduler means further examining said forthcoming high level language procedure calls and estimating said worst case time duration required to finish said forthcoming high level language procedure calls.