From: Patrick Moran <pmoran@nas.nasa.gov>

Date: Tue Sep 2, 2003 4:29:46 PM US/Pacific

To: John Shalf <jshalf@lbl.gov>

Cc: diva@lbl.gov

Subject: Re: DiVA Survey (Please return by Sept 10!)

Reply-To: patrick.j.moran@nasa.gov

On Wednesday 27 August 2003 03:33 pm, you wrote:

John,

Here's my couple cents worth:

=============The Survey=========================

Please answer the attached survey with as much or as little verbosity

as you please and return it to me by September 10. The survey has 3

mandatory sections and 4 voluntary (bonus) sections. The sections are

as follows;

Mandatory;

1) Data Structures

2) Execution Model

3) Parallelism and Load-Balancing

Voluntary;

4) Graphics and Rendering

5) Presentation

6) Basic Deployment and Development Environment Issues

7) Collaboration

We will spend this workshop focusing on the first 3 sections, but I

think we will derive some useful/motivating information from any

answers to questions in the voluntary sections.

I'll post my answers to this survey on diva mailing list very soon.

You can post your answers publicly if you want to, but I am happy to

regurgitate your answers as "anonymous contributors" if it will enable

you to be more candid in your evaluation of available technologies.

1) Data Structures/Representations/Management==================

The center of every successful modular visualization architecture has

been a flexible core set of data structures for representing data that

is important to the targeted application domain. Before we can begin

working on algorithms, we must come to some agreement on common methods

(either data structures or accessors/method calls) for exchanging data

between components of our vis framework.

There are two potentially disparate motivations for defining the data

representation requirements. In the coarse-grained case, we need to

define standards for exchanging data between components in this

framework (interoperability). In the fined-grained case, we want to

define some canonical data structures that can be used within a

component -- one developed specifically for this framework. These two

use-cases may drive different set of requirements and implementation

issues.

* Do you feel both of these use cases are equally important or should

we focus exclusively on one or the other?

I think both cases are important, but agreeing upon the fine-grained access

will be harder.

* Do you feel the requirements for each of these use-cases are aligned

or will they involve two separate development tracks? For instance,

using "accessors" (method calls that provide abstract access to

essentially opaque data structures) will likely work fine for the

coarse-grained data exchanges between components, but will lead to

inefficiencies if used to implement algorithms within a particular

component.

* As you answer the "implementation and requirements" questions below,

please try to identify where coarse-grained and fine-grained use cases

will affect the implementation requirements.

I think the focus should be on interfaces rather than data structures. I

would advocate this approach not just because it's the standard

"object-oriented" way, but because it's the one we followed with FEL,

and now FM, and it has been a big win for us. It's a significant benefit

not having to maintain different versions of the same visualization

technique, each dedicated to a different method for producing the

data (i.e., different data structures). So, for example, we use the same

visualization code in both in-core and out-of-core cases. Assuming up

front that an interface-based approach would be too slow is, in my

humble opinion, classic premature optimization.

What are requirements for the data representations that must be

supported by a common infrastructure. We will start by answering Pat's

questions of about representation requirements and follow up with

personal experiences involving particular domain scientist's

requirements.

Must: support for structured data

Structured data support is a must.

Must/Want: support for multi-block data?

Multi-block is a must.

Must/Want: support for various unstructured data representations?

(which ones?)

We have unstructured data, mostly based on tetrahedral or prismatic meshes.

We need support for at least those types. I do not think we could simply

graft unstructured data support on top of our structured data structures.

Must/Want: support for adaptive grid standards? Please be specific

about which adaptive grid methods you are referring to. Restricted

block-structured AMR (aligned grids), general block-structured AMR

(rotated grids), hierarchical unstructured AMR, or non-hierarchical

adaptive structured/unstructured meshes.

Adaptive grid support is a "want" for us currently, probably eventually

a "must". The local favorite is CART3D, which consists of hierarchical

regular grids. The messy part is that CART3D also supports having

more-or-less arbitrary shapes in the domain, e.g., an aircraft fuselage.

Handling the shape description and all the "cut cell" intersections

I expect will be a pain.

Must/Want: "vertex-centered" data, "cell-centered" data?

other-centered?

Most of the data we see is still vertex-centered. FM supports other

associations, but we haven't used them much so far.

Must: support time-varying data, sequenced, streamed data?

Support for time-varying data is a must.

Must/Want: higher-order elements?

Occasionally people ask about it, but we haven't found it to be a "must".

Must/Want: Expression of material interface boundaries and other

special-treatment of boundary conditions.

We don't see this so much. "Want", but not must.

* For commonly understood datatypes like structured and unstructured,

please focus on any features that are commonly overlooked in typical

implementations. For example, often data-centering is overlooked in

structured data representations in vis systems and FEM researchers

commonly criticize vis people for co-mingling geometry with topology

for unstructured grid representations. Few datastructures provide

proper treatment of boundary conditions or material interfaces. Please

describe your personal experience on these matters.

One thing left out of the items above is support for some sort of "blanking"

mechanism, i.e., a means to indicate that the data at some nodes are not

valid. That's a must for us. For instance, with Earth science data we see

the use of some special value to indicate "no data" locations.

* Please describe data representation requirements for novel data

representations such as bioinformatics and terrestrial sensor datasets.

In particular, how should we handle more abstract data that is

typically given the moniker "information visualization".

"Field Model" draws the line only trying to represent fields and the meshes

that the fields are based on. I not really familiar enough with other types

of data to know what interfaces/data-structures would be best. We haven't

see a lot of demand for those types of data as of yet. A low-priority "want".

What do you consider the most elegant/comprehensive implementation for

data representations that you believe could form the basis for a

comprehensive visualization framework?

* For instance, AVS uses entirely different datastructures for

structure, unstructured and geometry data. VTK uses class inheritance

to express the similarities between related structures. Ensight treats

unstructured data and geometry nearly interchangably. OpenDX uses more

vector-bundle-like constructs to provide a more unified view of

disparate data structures. FM uses data-accessors (essentially keeping

the data structures opaque).

Well, as you'd expect, as the primary author of Field Model (FM) I think it's

the most elegant/comprehensive of the lot. It handles structured and

unstructured data. It handles data non-vertex-centered data. I think it

should be able to handle adaptive data, though it hasn't actually been

put to the test yet. And of course every adaptive mesh scheme is a little

different. I think it could handle boundary condition needs, though that's

not something we see much of.

* Are there any of the requirements above that are not covered by the

structure you propose?

Out-of-core? Derived fields? Analytic meshes (e.g., regular meshes)?

Differential operators? Interpolation methods?

* This should focus on the elegance/usefulness of the core

design-pattern employed by the implementation rather than a

point-by-point description of the implemenation!

I think if we could reasonably cover the (preliminary) requirments above,

that would be a good first step. I agree with Randy that whatever we

come up with will have to be able to "adapt" over time as our understanding

moves forward.

* Is there information or characteristics of particular file format

standards that must percolate up into the specific implementation of

the in-memory data structures?

In FM we tried hard to file-format-specific stuff out of the core model.

Instead, there are additional modules built on top of FM that handle

the file-format-specific stuff, like I/O and derived fields specific to

a particular format. Currently we have PLOT3D, FITS, and HDFEOS4

modules that are pretty well filled out, and other modules that are

mostly skeletons at this point.

We should also be careful not to assume that analyzing the data starts

with "read the data from a file into memory, ...". Don't forget out-of-core,

analysis concurrent with simulation, among others.

One area where the file-format-specific issues creep in is with metadata.

Most file formats have some sort of metadata storage support, some much

more elaborate than others. Applications need to get at this metadata,

possibly through the data model, possibly some other way. I don't have

the answer here, but it's something to keep in mind.

For the purpose of this survey, "data analysis" is defined broadly as

all non-visual data processing done *after* the simulation code has

finished and *before* "visual analysis".

* Is there a clear dividing line between "data analysis" and "visual

analysis" requirements?

Your definition excludes concurrent analysis and steering from

"visualization". Is this intentional? I don't think there's a clear dividing

line here.

* Can we (should we) incorporate data analysis functionality into this

framework, or is it just focused on visual analysis.

I think you would also want to include feature detection techniques. For

large data analysis in particular, we don't want to assume that the scientist

will want to do the analysis by visually scanning through all the data.

* What kinds of data analysis typically needs to be done in your

field? Please give examples and how these functions are currently

implemented.

Around here there is interest in vector-field topology feature detection

techniques, for instance, vortex-core detection.

* How do we incorporate powerful data analysis functionality into the

framework?

Carefully :-)? By striving not to make a closed system.

2) Execution Model=======================

It will be necessary for us to agree on a common execution semantics

for our components. Otherwise, while we might have compatible data

structures but incompatible execution requirements. Execution

semantics is akin to the function of protocol in the context of network

serialization of data structures. The motivating questions are as

follows;

* How is the execution model affected by the kinds of

algorithms/system-behaviors we want to implement.

In general I see choices where at one end of the spectrum we have

simple analysis techniques where most of the control responsibilities

are handled from the outside. At the other end we could have more

elaborate techniques that may handle load balancing, memory

management, thread management, and so on. Techniques towards

the latter end of the spectrum will inevitably be intertwined more

with the execution model.

* How then will a given execution model affect data structure

implementations

Well, there's always thread-safety issues.

* How will the execution model be translated into execution semantics

on the component level. For example will we need to implement special

control-ports on our components to implement particular execution

models or will the semantics be implicit in the way we structure the

method calls between components.

Not sure.

What kinds of execution models should be supported by the distributed

visualization architecture

* View dependent algorithms? (These were typically quite difficult to

implement for dataflow visualization environments like AVS5).

Not used heavily here, but would be interesting. A "want".

* Out-of-core algorithms

A "must" for us.

* Progressive update and hierarchical/multiresolution algorithms?

A "want".

* Procedural execution from a single thread of control (ie. using an

commandline language like IDL to interactively control an dynamic or

large parallel back-end)

Scripting support is a "must".

* Dataflow execution models? What is the firing method that should be

employed for a dataflow pipeline? Do you need a central executive like

AVS/OpenDX or, completely distributed firing mechanism like that of

VTK, or some sort of abstraction that allows the modules to be used

with either executive paradigm?

Preferably a design that does not lock us in to one execution model.

* Support for novel data layouts like space-filling curves?

Not a pressing need here, as of yet.

* Are there special considerations for collaborative applications?

* What else?

Distributed control? Fault tolerance?

How will the execution model affect our implementation of data

structures?

* how do you decompose a data structure such that it is amenable to

streaming in small chunks?

Are we assuming streaming is a requirement?

How do you handle visualization algorithms where the access patterns

are not known a priori? The predominant example: streamlines and streaklines.

Note the access patterns can be in both space and time. How do you avoid

having each analysis technique need to know about each possible data

structure in order to negotiate a streaming protocol? How do add another

data structure in the future without having to go through all the analysis

techniques and put another case in their streaming negotiation code?

In FM the fine-grained data access ("accessors") is via a standard

interface. The evaluation is all lazy. This design means more

function calls, but it frees the analysis techniques from having to know

access patterns a priori and negotiate with the data objects. In FM

the data access methods are virtual functions. We find the overhead

not to be a problem, even with relatively large data. In fact, the overhead

is less an issue with large data because the data are less likely to be

served up from a big array buffer in memory (think out-of-core, remote

out-of-core, time series, analytic meshes, derived fields, differential-

operator fields, transformed objects, etc., etc.).

The same access-through-an-interface approach could be done without

virtual functions, in order to squeeze out a little more performance, though

I'm not convinced it would be worth it. To start with you'd probably end up

doing a lot more C++ templating. Eliminating the virtual functions would

make it harder to compose things at run-time, though you might be able

to employ run-time compilation techniques a la SCIRun 2.

* how do you represent temporal dependencies in that model?

In FM, data access arguments have a time value, the field interface is

the same for both static and time-varying data.

* how do you minimize recomputation in order to regenerate data for

view-dependent algorithms.

Caching? I don't have a lot of experience with view-dependent algorithms.

What are the execution semantics necessary to implement these execution

models?

* how does a component know when to compute new data? (what is the

firing rule)

* does coordination of the component execution require a central

executive or can it be implemented using only rules that are local to a

particular component.

* how elegantly can execution models be supported by the proposed

execution semantics? Are there some things, like loops or

back-propagation of information that are difficult to implement using a

particular execution semantics?

The execution models we have used have kept the control model in

each analysis technique pretty simple, relying on an external executive.

The one big exception is with multi-threading. We've experimented with

more elaborate parallelism and load-balancing techniques, motivated in

part by latency hiding desires.

How will security considerations affect the execution model?

More libraries to link to? More latency in network communication?

3) Parallelism and load-balancing=================

Thus far, managing parallelism in visualization systems has been a

tedious and difficult at best. Part of this is a lack of powerful

abstractions for managing data-parallelism, load-balancing and

component control.

Please describe the kinds of parallel execution models that must be

supported by a visualization component architecture.

* data-parallel/dataflow pipelines?

* master/slave work-queues?

* streaming update for management of pipeline parallelism?

* chunking mechanisms where the number of chunks may be different from

the number of CPU's employed to process those chunks?

We're pretty open here. Mostly straight-forward work-queues.

* how should one manage parallelism for interactive scripting

languages that have a single thread of control? (eg. I'm using a

commandline language like IDL that interactively drives an arbitrarily

large set of parallel resources. How can I make the parallel back-end

available to a single-threaded interactive thread of control?)

I've used Python to control multiple execution threads. The (C++)

data objects are thread safe, the minimal provisions for thread-safe

objects in Python haven't been too much of a problem.

Please describe your vision of what kinds of software support /

programming design patterns are needed to better support parallelism

and load balancing.

* What programming model should be employed to express parallelism.

(UPC, MPI, SMP/OpenMP, custom sockets?)

* Can you give some examples of frameworks or design patterns that you

consider very promising for support of parallelism and load balancing.

(ie. PNNL Global Arrays or Sandia's Zoltan)

http://www.cs.sandia.gov/Zoltan/

http://www.emsl.pnl.gov/docs/global/ga.html

* Should we use novel software abstractions for expressing parallelism

or should the implementation of parallelism simply be an opaque

property of the component? (ie. should there be an abstract messaging

layer or not)

* How does the NxM work fit in to all of this? Is it sufficiently

differentiated from Zoltan's capabilities?

I don't have a strong opinion here. I'm not familiar with Zoltan et al.

Our experience with parallelism tends to be more shared-memory than

distributed memory.

===============End of Mandatory Section (the rest is

voluntary)=============

Laziness prevails here, so I'll stop for now :-).

Pat