3.14. PIEMON-1

PIEMON-1 is an initial implementation of the PIE project [Greg85] which focus on the programming-for-observability concept. This concept addresses performance and correctness in debugging in a parallel programming environment. Therefore, it serves as a feasibility study on programming for observability in PIE. According to Gregoretti and Segall,

PIE - The Programming and Instrumentational Environment project ... is geared equally towards a system intensive rather than programmer intensive parallel programming, and towards the support of performance efficient parallel programs. ... The second approach is performance debugging through the concept of programming for observability. ... The programming for observability approach encourages and provides support for designing and implementing a program with the goal of correctness and performance debugging in mind.

One of the major components of PIE is its Parallel Programming Metalanguage (MP) which allows the encapsulation of parallel program's elements. In MP, sequential code is organized as an activity, which is the smallest unit of schedulable work. Operations with shared memory are specified in a frame. A team contains concurrent activities with shared frames. A team is also a unit of schedulable work. The MP specifications and directives are called sensors. Sensors allow the expression, through basic language level mechanisms, of program observability. Figure 3.37 shows the basic components of an MP team.

* Team

o Definitions. (Statically scoped)

* Activity Definitions. A complete program in an extended serial programming language. Monitoring directives concerning aspects of the activity state. Points in the program marked as events with associated names.

* Abstract Shared Data Type Definitions. These describe the shared declarations, the hidden and the visible operations, and the access control of these operations. A data initialization specification can also be supplied. Monitoring directives concerning the values of the shared constructs as well as monitoring the time spent waiting for synchronization.

* Team Definitions. The definition provides static scoping of the logical entities.

o Body

* Activities. The set of activities that are to be executed in parallel when the team is invoked along with a repetition count indicating that there are to be multiple copies of the activity.

* Frames. Binds names to instances of the shared data types. This represents the data that is common to all activities and frames in this scope.

o Control

* Activity Control. Generalized path expressions specifying initiation and terminating conditions for the activities and for the team. Constraints are specified in terms of instances of the entities, global variables and events.

* Resource Allocation. Mapping activity instantiation to processors; for each instance of an activity either a specific processor is suggested, or the system is free to allocate as it pleases. Where shared memory is to be allocated and whether or not the pages can be swapped is specified.

* Monitoring Directives. Specifications as to whether any particular configuration of the activities should be noted. The system, by default, monitors the initiation and termination of each instance of a team.

Figure 3.37 - Figure Team: A Summary of the Modules and their Meaning for the Specification of a Parallel Program in the MP Environment

In PIEMON-1 monitoring is accomplished by inserting software sensors into the run-time support and also into the program's source code. A notification mechanism permits all sensors to pass the collected information as messages to an accounting process which is executed in parallel with the application. The messages are stored temporarily in a file. MP uses a relational database (RDB) as a vehicle to provide both the integration of the monitoring mechanism and the selective retrieval of information. Figure 3.38 shows the structure of the PIEMON-1 notification mechanism. According to Gregoretti and Segall,

In the RDB there are three predefined primitive types of relation:

- The Events relation whose domains have the same format as sensors notifications and whose entries are filled by the accountant process at the end of an experiment. The relation contents is updated at every execution of the parallel program.

- The Objects relation whose entries are the MP objects (Teams, Frames and Activities) defined in the parallel program. The domains of this relation are the static name of the object, its type and the name of its parent object. The relation is created at program development time by the MPOE environment and its contents are modified whenever the source program is modified.

- The sensors relation whose domains are sensor name, its type and subtype, the static name of the object in which it is placed and a pointer to source code inside the object

. This relation too is created by the MP environment at program development time and contains an entry for every sensor inserted by the user in the application code or embedded into the run time support.

Four views are provided: roadmap, activity execution times, invocation tree, and frame usage tree. Figure 3.39 shows the roadmap view. The roadmap view shows the objects' relations at development time. By selecting an object within this view, the user is given a view of the related part of the code. This feature is possible because of the integration between the roadmap and the MPOE.

Figure 3.38 - The Structure of the Notification Mechanism

Figure 3.39 - The Roadmap View

Figure 3.40 shows the activity execution times view. A bar graph is used to show the execution times related to the instances of an activity.

Figure 3.40 - Activity Execution Times

Figure 3.41 shows the invocation tree view. This view attempts to represent the dynamic invocation sequence of the experiment's components (teams, activities, and frames). The picture is displayed in reduced speed so that the user can select an object for a MPOE inspection.

Figure 3.41 - Invocation Tree View

Figure 3.42 shows the frame usage view. This view shows activities accessing shared memory at run-time. It is intended to aid in the identification of blottlenecks caused by contention for common objects.

Figure 3.42 shows the frame usage view. This view shows activities accessing shared memory at run-time. It is intended to aid in the identification of blottlenecks caused by contention for common objects.

Figure 3.42 - The Frame Usage View

3.14. An Intention-Based Diagnosis System - PROUST

PROUST analyzes Pascal programs for non-syntactic bugs. According to Johnson [Jhon86] "the process of identifying faults in designed artifacts is called intention-based diagnosis."

When intention-based diagnosis is used, bugs are identified by attempting to understand the proposed behavior of an artifact. In the case of PROUST, Pascal programs are the artifacts. This "understanding" is achieved by using the description of the problem which is called a plan. According to Johnson,

programming plans describe stereotypical action sequences in programs ... programming plans facilitate the understanding of programs by providing background knowledge or context.

PROUST was designed as a debugging tool for assisting novice programmers under the guidance of an instructor. The instructor must prepare a plan for each assigned program. The program being debugged by PROUST is matched against a knowledge base of plans. The following example shows how PROUST works through a sequence of figures. Figure 3.43 shows the description of problem called the Bank Problem [Jhon86] which is given to the students.

Write a Pascal program that processes three types of bank transactions: withdrawals, deposits, and a special transaction that says: no more transactions are to follow. Your program should start by asking the user to input his/her account id and his/her initial balance. Then your program should prompt the user to input

1. the transaction type, and

2. if it is an END-PROCESSING transaction the program should print out the (a) final balance of the user's account, (b) the total number of transactions, and (c) total number of each type of transaction, and (d) the total amount of the service charges, and stop;

3. if it is a DEPOSIT or a WITHDRAWAL, the program should ask for the amount of the transaction and then post it appropriately.

Use a variable of type CHAR to encode the transaction types. To encourage saving, charge the user 20 cents per withdrawal, but nothing for a deposit.

Figure 3.43 - The Bank Problem Description

Figure 3.44 shows an example for a solution to the Bank problem.

1 program BankA(input,output);

2 const Srvc = 0.20;

3 var Number, TypeW, TypeD, Acct: integer;

4 Deposit, Withdrawal, Balance: real;

5 TransType: char;

6 begin

7 TypeD := 0;

8 TypeW := 0;

9 writeln('Enter account number, please');

10 readln(Acct);

11 writeln('Enter initial balance');

12 readln(Balance);

13 writeln('Enter type of transaction, w for withdrawal');

14 writeln('d for deposit and e for end-processing');

15 readln(TransType);

16 while(TransType <> 'e') do begin

17 if TransType = 'w' then

18 begin

19 writeln('Enter amount of withdrawal:');

20 readln(Withdrawal);

21 if (Withdrawal >= 0) and (Withdrawal <= Balance - Srvc) then

22 begin

23 Typew:= Typew + 1;

24 Balance:= (Balance - Withdrawal_ - Srvc;

25 writeln('New balance:', Balance:1:2);

26 end

27 else

28 if Withdrawal > Balance

29 then writeln('Sorry, short of funds')

30 else

31 writeln('No negative withdrawals');

32 end

33 else if TransType= 'd' then

34 begin

35 writeln('Enter amount of deposit:');

36 readln(Deposit);

37 if Deposit >= 0 then

38 begin

39 typed:= typed + 1;

40 Balance:= Balance + Deposit;

41 writeln("New balance:', Balance:1:2);

42 end

43 else

44 writeln('No negative deposits');

45 end

46 else writeln('sorry, type must be w, d or e');

47 end;

48 writeln('Transactions completed');

Figure 3.44 - An Example Solution to the Bank Problem

DefProgram Bank;

DefObject ?Bank:InData

Type char, ObjectClass SingleLetterCommand,

Range Multivalued, Values (?Bank:DTrans, ?Bank:WTrans, ?Bank:Etrans);

DefObject ?Bank:Dtrans Value 'd';

DefObject ?Bank:Wtrans Value 'w';

DefObject ?Bank:Etrans Value 'e';

DefObject ?Bank:AccID ObjectClass AccountNumber, Range Multivalued;

DefObject ?Bank:Balance ObjectClass AccountBalance, Range Multivalued;

DefObject ?Bank:Deposit ObjectClass TransactionAmount, Range Multivalued;

DefObject ?Bank:WithDrawal ObjectClass WithdrawalAmount, Range MultiValued;

DefObject ?Bank:Charge ObjectClass DollarAmount, Value 0.20;

DefObject ?Bank:WithdrawalCount ObjectClass NaturalNumber, Range MultiValued;

DefObject ?Bank:DepositCount ObjectClass NaturalNumber, Range MultiValued;

DefObject ?Bank:TotalCharge ObjectClass DollarAmount, Range MultiValued;

DefObject ?Bank:TotalCount ObjectClass NaturalNumber, Range MultiValued;

DefGoal Input1 = Input(?Bank:AccID);

DefGoal Input2 = Input(?Bank:Balance);

DefGoal Loop1 = Sentinel-Controlled Input Sequence (?Bank:InData, ?Bank:ETrans);

Input1 Precedes Loop1;

Input2 Precedes Loop1;

DefGoal When(?Bank:Indata = ?Bank:Dtrans,GoalBlock(Input (?Bank:Deposit);

Accumulate(?Bank:Balance, ?Bank:Deposit);

Bind ?Bank:DepositCount = Count(?Bank:InData)));

DefGoal when(?Bank:InData = ?Bank:WTrans, GoalBlock(Input(?Bank:WithDrawal);

CompoundDeduct(?Bank:WithDrawal, ?Bank:Charge, ?Bank:Balance);

GuardException(Update: component of CompoundDeduct,

?Bank:WithDrawal >= ?Bank:Balance - ?Bank:Charge);

Bind ?Bank:TotalCharg = ConstantSum(?Bank:Charge));

Bind ?Bank:WithdrawalCount = Count(?Bank:InData));

Bind ?Bank:TotalCount = Count(?Bank:InData);

DefGoal Output(?Bank:TotalCharge);

DefGoal Output(?Bank:TotalCount);

DefGoal Output(?Bank:DepositCount);

DefGoal Output(?Bank:WithdrawalCount);

Figure 3.45 - A Plan for the Bank Problem

When submitting the program shown in Figure 3.44, PROUST uses the plan that is shown in Figure 3.45. As a result of its analysis, PROUST issues the bug report shown in Figure 3.46.

NOW BEGINNING BUG REPORT

(TO CONTINUE, PLEASE PRESS CARRIAGE RETURN)

 

>>> Now Reporting MINOR Bugs in the SETUP part:

There is no input validation for the variables ACCT and BALANCE.

(TO CONTINUE, PLEASE PRESS CARRIAGE RETURN)

 

>>> Now Reporting CRITICAL Bugs in the CONTROL part:

There is no input validation for the variable TRANSTYPE.

Your main loop is missing a READ statement. As it stands

your loop will process the same input value over and over.

(TO CONTINUE, PLEASE PRESS CARRIAGE RETURN)

 

>>> Now Reporting MINOR Bugs in the CONTROL part:

Your test at line 24 permits zero transactions. You may

disagree, but I think they should be excluded.

The statement in question is:

IF AMOUNT >= 0 AND AMOUNT <= BALANCE THEN ... ELSE ...

Your test at line 41 permits zero transactions. You may

disagree, but I think they should be excluded.

The statement in question is:

IF AMOUNT >= 0 THEN ... ELSE ...

BUG REPORT NOW COMPLETE.

Figure 3.46 - The Diagnosis Issued for the Bank Program

3.15. Discussion and Comparison of Related Work

While most of the work cited above focuses on concurrent programming issues, its approach is markedly different from that of the present research. Some of the tools,mentioned above, such as DbxTool [Adam86] and YODA [Ledo85], allow the programmer to inspect the program state through low-level debugging features by setting break points, examining the data and performing queries about program activity.

Table 3.1 shows a classification for the above tools based on the type of help given to the programmer. The column labeled HELP indicates the nature of help that a given tool provides. A Type 1 tool does not provide the kind of help provided by a Type 2 tool. Tools that provide the user with similar instruments for detecting sequential bugs are said to be of Type 1. DbxTool and YODA are examples of Type 1 tools. Other tools show the programmer different graphical views of the program activity. Examples of these are MORAN [More85], CPEM [Male88], MAD [Rubi89], and VESTAL [Toma91]. These four tools are defined as Type 2. None of the above systems perform any sort of analysis, such as static analysis or dynamic analysis. The programmer plays a major role in the detection and elimination of a bug. Yet another class of tools requires the programmer to specify how he or she wants to observe the program while in execution. Examples of such systems are BELVEDERE [Houg89] and PIEMON-1 [Greg85]. These two tools are defined as Type 3. Departing from this approach of inspection and observation are tools that analyze the program's behavior and detect the occurrence of a problem related to concurrency. Through a snapshot, these tools report to the user the elements involved in the problem. Examples of such tools are MON [Luck85], EDEN [Chen87] and PPD [Mill88]. These three tools are defined as Type 4.

A fifth and distinct approach is to analyze a program, report to the programmer what is wrong, and offer solutions as to how the bug can be corrected, rather than just showing what is related to a fault. In the literature review, no such tool was found for concurrent programs. PROUST [John86] takes this helpful approach, but was designed for sequential programs. This tool type is defined as Type 5. A severe limitation of PROUST is that a complete plan must be inserted into a knowledge base of plans in order for a program to be debugged. Each program is associated with a plan. A new program can not use already defined plans.

Among all of the above tools, VESTAL was the only one designed for teaching concurrency.

Table 3.1 - Tools and the Kind of Help Given

The work of Anderson [Ande83, 87, 88], Soloway and Johnson [Solo88, John85] provides the basis for studies related to the emerging field of empirical studies of programmers. Their work focused on sequential programming and the debugging process, as used in PROUST, and is based on plans. This research addresses similar issues, but related to concurrency and using a different approach. A bug is identified and the user is guided to eliminate it without the use of plans. This approach is discussed in Chapters Four, Five and Six.