. The program implements a dictionary
search in which queries are pipelined from a host to a database of key-ordered
records stored in a hypercube. Queries are routed within
the cube to the proper node using binary search. More than one query is
active at a time. The program as written contained a routing error.
We consider an 8 processor hypercube with processors having PIDs 0 to 7, and
a host process with PID 8. We model the behavior of the program as a series
of queries, each query starting at the host, traversing the cube, and eventually
returning to the host. Each query has two parts to it: the first is the
routing of the query from the host to the appropriate node ( Find phase),
and the second is the
routing of the reply to the host from the answering node ( Reply phase).
The messages that are sent as a part of the Find phase are tagged
as ``ask'' messages, and the messages that are part of the Reply
phase are tagged as ``ans'' messages. The routing of the
query from the host to the appropriate node should be according to the binary
search pattern, the routing of the response should follow the shortest path
between the node and the host. The behavioral model is described using Ariadne
as follows:
? set cube = {0 .. 7};
? ch ask = (W_ask @ R_ask) ;
? ch ans = (W_reply @ R_reply) ;
? pch Find = ask+ onall {8};
? pch Reply = ans+ onsome cube;
? match Query = (Find Reply)+;
The behavioral description defines a set cube of integers 0 to 7. These are the PIDs of the processors that make the hypercube. The chain ask defines a single message of the Find phase, and ans defines a single message of the Reply phase. A query is composed of a Find followed by a Reply. The pchain Find starts with matching a message tagged as ``ask'' on processor 8, and follows the subsequent messages tagged ``ask'' until it reaches the processor, that answers the query with a message tagged as ``ans''. Since the identity answering processor is not known beforehand, onsome specifies that the Reply phase should start on one of the processor in the hypercube. The Ave feedback is shown below:
Figure: Ave feedback in the dictionary search example.
The feedback shows that the match is composed of 2 queries. The first question
took 5 hops to reach the appropriate node as is shown by the feedback
ask^5 and took 5 hops to reach the host
processors from the answering node as evidenced by the feedback
ans^5. Note that the distance of the host
processor from any answering node can atmost be one greater than the degree of the
hypercube, in our case of a 8 node hypercube, the distance should
not be greater than 4. Since the answer of a query is supposed to be
routed to the host through the shortest path, clearly there is an error
in the routing code. The first part of the query (from the host to the
appropriate node) follows the binary search pattern which may involve
backtracking: so 5 hops in search of the appropriate node is not an error.
The combined power of the visual feedback scheme (Ave) and
the hierarchical modeling approach (Ariadne) not only reveals the bug
but makes it possible to hint at its location
(routing code specific to the answer).