There was a lot of controversy over what constituted an object when object programming was initially introduced. There is a similar controversy over exactly what constitutes an agent. Many proponents define agents as autonomous continuously executing programs that act on behalf of a user. However, this definition can be applied to some Unix daemons or even some device drivers. Others add the requirements that the agent must have special knowledge of the user, must execute in an environment inhabited by other agents, and must function only within the specified environment. These requirements would exclude other programs considered to be agents by some. For instance, many e-mail agents act alone and may function in multiple environments. In addition to agent requirements, various groups in the agent community have introduced terms like softbot, knowbot, software broker, and smart object to describe agents. One commonly found definition defines an agent as "an entity that functions continuously and autonomously in an environment in which other processes take place and other agents exist."

Although it is tempting to accept this definition and move on, we cannot because it too easily describes other kinds of software constructions. A more formal source, the Foundation for Intelligent Physical Agents (FIFA) specification, defines the term agent as follows: "An Agent is the fundamental actor in a domain. It combines one or more service capabilities into a unified and integrated execution model which can include access to external software, human users and communication facilities."

While this definition has a more structured feel, it also needs further clarification because many servers (some Object-Oriented and some that are not) fit this definition. This definition as is would include too many types of programs and software constructs to be useful. In our PADL model we use the five-part definition of agents as stated by [Luger, 2002]:

We use the term multiagent architecture when referring to an agent-based architecture that consists of two or more agents that can execute concurrently if necessary. It should be clear from Luger's definition of agents that multiagent architecture can be used as an extremely flexible approach to patterns of work that require or can benefit from concurrency. Notice in this definition of agents that there is no mention of particular computer capabilities, numbers of processors, thread management, or so forth. There is also no limit on the number of agents involved. There are no complexity constraints on the patterns of work that a collection of agents can perform. If you begin with the blueprint that is consistent with a multiagent architecture, you should be able to handle concurrency of any size.

Decomposition is one of the primary challenges in software development. It is more of a challenge when the software development requires parallel programming. Our approach to this challenge is to find an appropriate model of the problem and appropriate solution model. Using PADL analysis, we select an application architecture based on the solution model. To see how this works, consider again the guess-what-code-I'm-thinking problem from Chapter 4.

Recall the game scenario from Chapter 4 goes as follows: I'm thinking of a six-character code. My code can contain any character more than once. However, my code can only contain any characters from the numbers 0-9 or characters a-z. Your job is to guess what code I have in mind. In the game the buzzer is set to go off after 5 minutes. If you guess what I'm thinking in 5 minutes you win. In that chapter, we determined that you have 4,496,388 possible codes to choose from.

Now, in this simple example, we want to make the game a little more challenging. You now have only 2 minutes to guess. In addition to this, instead of making up a code, I am handed the initial code by my trusted assistant. If my assistant determines that you have made more than N incorrect guesses within a 15-second interval, my assistant hands me a new code, and the new code is guaranteed to be among the guesses that you have already made.

(n −1 + r)! / (n-1)!r!

Problem and Solution Model as Multiagents

You can easily see from the statement of the problem that you are initially dealing with three agents. If you recast the game in terms of agents you have the following: Agent A gives the code to Agent B. Agent C tries to guess Agent B's code. If Agent C comes up with too many guesses in a 15-second interval, Agent A will give Agent B a new code that is guaranteed to be a code that Agent C has already presented. If Agent C is able to go through all of the possibilities and is still not declared the winner and if Agent C has more time left, that agent will make the same guesses only faster. Agent C realizes that in order to generate enough guesses to guarantee success within the given time limit will require help. So, Agent C recruits a team of agents to help him come up with guesses. For each pass through the total possibilities, Agent C recruits a bigger team of agents to help with the guesses.

Obviously, you could now start thinking in terms of agents mapped to either threads or processes. But we will resist this temptation. You do not want to think in terms of threads and processes at this level. In the PADL model approach, you work out a complete and correct logical statement of the application in Layers 5 and 4. So, before proceeding to Layer 4, if you are applying the PADL model to the game scenario, you refine the relationships and interactions of all of the agents involved. The assumption and conditions that the agents operated under would all be made clear. A complete picture of the multiagent interaction would be given. Figure 8-2 is a UML activity diagram that captures the interaction of the micro-multiagent society.

Figure 8.2. Figure 8-2

The Blackboard model is an approach to collaborative problem solving. The Blackboard is used to record, coordinate, and communicate the efforts of two or more software-based problem solvers. There are two primary types of components in the Blackboard model.

The Blackboard is a centralized object that each of the problem solvers has access to. The problem solvers may read the Blackboard and change the contents of the Blackboard. The contents of the Blackboard at any given time will vary. The initial content of the Blackboard will include the problem to be solved.

In addition to the problem to be solved, other information representing the initial state of the problem, problem constraints, goals, and objectives may be contained on the Blackboard. As the problem solvers are working toward the solution, intermediate results, hypotheses, and conclusions are recorded on the Blackboard. The intermediate results written by one problem solver on the Blackboard may act as catalyst for other problem solvers reading the Blackboard. Tentative solutions are posted to the Blackboard. If the solutions are determined not to be sufficient, these solutions are erased, and other solutions are pursued. The problem solvers use the Blackboard as opposed to direct communication to pass partial results and findings to each other. In some configurations, the Blackboard acts as a referee, informing the problem solvers when a solution has been reached or when to start work or stop work. The Blackboard is an active object, not simply a storage location. In some cases, the Blackboard determines which problem solvers to involve and what content to accept or reject. The Blackboard may also organize the incremental or intermediate results of the problem solvers. The Blackboard may translate or interpret the work from one set of problem solvers so that it can be used by another set of problem solvers.

The problem solver is a piece of software that typically has specialized knowledge or processing capabilities within some area or problem domain. The problem solver can be as simple a routine that converts from Celsius to Fahrenheit or as complex as a smart agent that handles medical diagnosis. In the Blackboard model, these problem solvers are called knowledge sources (KS). To solve a problem using Blackboards, you need two or more knowledge sources, and each knowledge source usually has a specific area of focus or specialty. The Blackboard is a natural fit for problems that can be divided into separate tasks that can be solved independently or semi-independently. In the basic Blackboard configuration each problem solver tackles a different part of the problem. Each problem solver only sees the part of the problem that it is familiar with. If the solutions to any parts of the problem are dependent on the solutions or partial solutions to other parts of the problem, then the Blackboard is used to coordinate the problem solvers and the integration of the partial solutions.

A Blackboard's problem solvers need not be homogeneous. Each problem solver may be implemented using different techniques. For instance, some problem solvers might be implemented using Object-Oriented techniques, while other solvers might be implemented as functions. Further the problem solvers may employ completely different problem-solving paradigms. For example, solver A might use a backward chaining approach to solving its problem, while solver B might use a counterpropagation approach. There is no requirement that the Blackboard's problem solvers be implemented using the same programming language.

The Blackboard model does not specify any particular structure or layout for the Blackboard. Neither does it suggest how the knowledge sources should be structured. In practice, the structure of a Blackboard is problem dependent. The implementation of the knowledge sources is also specific to the problem being solved. The Blackboard framework is a conceptual model describing relationships without describing the structures of the Blackboard and knowledge sources. The Blackboard model does not dictate the number or purpose of the knowledge sources. The Blackboard may be a single global object or a distributed object with components on multiple computers. Blackboard systems may even consist of multiple Blackboards, with each Blackboard dedicated to a part of the original problem. This makes the Blackboard an extremely flexible model for problem solving. The Blackboard model supports parallel programming and many of the concurrency models. The Blackboard can be segmented into separate parts, allowing concurrent access by multiple knowledge sources. The Blackboard easily supports Concurrent Read Exclusive Write (CREW), Exclusive Read Exclusive Write (EREW), and Multiple Instruction, Multiple Data (MIMD). The knowledge sources may execute simultaneously with each knowledge source working on its part of the problem.

Figure 8-3 shows two memory configurations for the Blackboard.

Figure 8.3. Figure 8-3

In both the cases in Figure 8-3, all knowledge sources have access to the Blackboard. This configuration provides for an extremely flexible model of problem solving.

As we have indicated, there is no one way to structure a Blackboard. However, most Blackboards have certain characteristics and attributes in common. The original contents of the Blackboard typically contain some kind of partitioning of the solution space for the problem that is to be solved. The solution space contains all the partial solutions and full solutions to a problem.

The Blackboard as an Iterative Shared Solution Space

The solution space is sometimes organized in a hierarchy. In the case of the question and answer processing example, valid question classifications would be at the top of the hierarchy, and the next level might consist of various views of the classifications. For example, with different forms for who, what, where, and when questions, each level describes a smaller perhaps less obvious aspect of a question classification (for example, is the verb transitive?). The knowledge sources may work on multiple levels within the hierarchy simultaneously. The solution space may also be organized as a graph where each node represents some part of the solution, and each edge represents the relationships between two partial solutions. The solution space may be represented as one or more matrices with each element of the matrix or matrices containing a solution or partial solution. The solution space representation is an important component of the Blackboard architecture. The nature of the problem will often determine how the solution space should be partitioned. This feature is critical in the PADL model because we use Layer 5 to describe the application architecture and the application architecture has to be flexible enough to map to the solution model. The structure of the Blackboard supports this flexibility.

In addition to a solution space component, Blackboards typically have one or more rule (heuristic) components. The rule component is used to determine which knowledge sources to deploy, and what solutions to accept or reject. The rule component can also be used to translate partial solutions from one level in the solution space hierarchy to another level. The rule component may also be used to prioritize the knowledge source approaches. The rule component supports concurrently among knowledge sources. This is the level where concurrency needs to be dealt with by using a declarative interpretation of parallel processing. Some knowledge sources might be going down blind alleys. The Blackboard deselects one set of knowledge sources in favor of another set. The Blackboard may use the rule component to suggest to the knowledge sources a more appropriate potential hypothesis based on the partial hypothesis already generated.

In addition to the solution space and rule component, the Blackboard often contains initial values, constraints values, and ancillary goals. In some cases, the Blackboard contains one or more event queues that are used to capture input from either the problem space or the knowledge sources. Figure 8-4 shows a logical layout for a basic Blackboard architecture.

Figure 8.4. Figure 8-4

Figure 8-4 shows that the Blackboard has a number of segments. Each segment in Figure 8-4 has a variety of implementations. This suggests that Blackboards are more than global pieces of memory or traditional databases. While Figure 8-4 shows the common core components that most Blackboards have, the Blackboard architecture is not limited to these components. Other useful components for Blackboards include context models of the problem and domain models that can be used to aid the problem solvers (KS) with navigation through the solution space. The support that C++ has for Object-Oriented Design and Programming fits nicely with the flexibility requirements of the Blackboard model. Most Blackboard architectures can be modeled using classes in C++. Recall that classes can be used to model some person, place, thing, or idea. Blackboards are used to solve problems that involve persons, places, things, or ideas. So, using C++ classes to model the objects that Blackboards contain or the actual Blackboards is a natural fit. We take advantage of C++ container classes and the standard algorithms in our implementations of the Blackboard model.

Knowledge sources are represented as objects, procedures, sets of rules, logic assertions, and in some cases entire programs. Knowledge sources have a condition part and an action part. When the Blackboard contains some information that satisfies the condition part of some knowledge source, the action part of the knowledge source is activated. Robert Englemore and Tony Morgan clearly state the responsibilities of a knowledge source in their work Blackboard Systems:

Here, Englemore and Morgan don't specify any of the details of the condition part or the action part of a knowledge source. They are logical constructs. The condition part could be as simple as the value of some boolean flag on the Blackboard or as complex as a specific sequence of events arriving in an event queue within a certain period of time. Likewise, the action part of a knowledge source can be a simple as a single statement performing an expression assignment or as involved as forward chain in an expert system. Again, this is a statement of how flexible the Blackboard model can be. The C++ class construct and the notion of an object are sufficient for our purposes. Each knowledge source will be an object (for sophisticated uses an object hierarchy). The action part of the knowledge source will be implemented by the object's methods. The condition part of the knowledge source will be captured as data members of the object. Once the object is in a certain state then the action parts of that object will be activated.

An important attribute of the knowledge source is its autonomy. Each knowledge source is a specialist and is largely independent from the other problem solvers. This presents one of the desired qualities for a parallel program. Ideally the tasks in a parallel program can operate concurrently without much interaction with other tasks. This is exactly the case in the Blackboard model. The knowledge sources act independently, and any major interaction is through the Blackboard. So, from the knowledge source's point of view, it is acting alone, getting additional information from the Blackboard, and recording its findings on the Blackboard. The activities of the other knowledge sources, their strategies, and structures are unknown. In the Blackboard model, the problem is partitioned into a number of autonomous or semi-autonomous program solvers. This is the advantage of the Blackboard model over other concurrency models. In the most flexible configuration, the knowledge sources are rational agents, meaning the agent is completely self-sufficient and able to act on its own with minimum interaction with the Blackboard. Rational agents in conjunction with Blackboards present the greatest opportunity for large scale parallelism or massively parallel CMPs. This use of rational agents as knowledge sources combines the two primary architectures from Layer 5 of PADL: multiagent architectures and Blackboard architectures. A full discussion of rational agents takes us beyond the scope of this book. However, we can say that rational agents fit into the category of agents that we discussed earlier in the chapter in the section "What Are Agents?" When knowledge sources are implemented as rational agents in large-scale systems, the rule and action components of the knowledge sources are learned using Inductive Logic Programming (ILP) techniques [Bergadano, Gunetti, 1996]. The ILP techniques provide a gateway to bottom-up declarative programming.

We move away from bottom-up procedural programming techniques and toward PADL in order to cope with complexity as the scale of available cores on CMP increases. However, bottom-up declarative programming using ILP or evolutionary programming techniques [Goertzel, Pennachin, 2007] is a legitimate part of the PADL analysis model. These approaches are used in Layer 3 where we are concerned with the availability and implementation of application frameworks, class libraries, algorithm templates, and so on.

Although there are many different types of software architectures that support parallelism, we use multiagent and Blackboard architectures in Layer 5 of PADL because of their general purpose nature and the range of concurrency models they support. Many different types of solutions that require concurrency can be expressed using multiagent or Blackboard architectures. Multiagent architectures and Blackboards are domain independent. They can be used in many different areas. Further, these architectures can be used for solutions of all sizes from small programs to large-scale, enterprise-wide solutions. While these architectures might be new to developers who are in the process of learning parallel or multithreaded programming techniques, they are well defined, and many useful resources that introduce the basic ideas of agents and Blackboards are available, see [Russell, Norvig, 2003], [Englemore, Morgan, 1988], [Goertzel, Pennachin, 2007], and [Fagin et al., 1996]. You will see that the selection of the architecture impacts software maintenance, testing, and debugging. Most successful software undergoes constant change. If that software has components that require concurrency and synchronization, then the natural evolution of the software can be extremely challenging if an appropriate application architecture was not selected from the start. The PADL analysis model presents two well-known and well-understood architectures that perform well under the conditions of software evolution. Ultimately, the concurrency of an application is going to be implemented by low-level operating system primitives like threads and processes. If the application architecture is clean, modular, scalable, and well understood, then the translation into manageable operating system primitives has a chance to succeed. On the other hand, selection of the wrong or a poor application architecture leads to brittle, error-prone software that cannot be readily changed, maintained, or evolved. While this is true of any kind of computer application, it is magnified when that software involves parallel programming, multithreading, or multiprocessing.

Fortunately, the C++ environment has an impressive set of features, libraries, and techniques that can be deployed for model implementation. We emphasize the word model here because parallelism and concurrency are best managed in the context of models. The seven steps shown in Figure 8-6 move from models of the problem to models of the solution and finally to implementation models. If you use declarative models in your solutions, then you can reliably develop software that takes advantage of medium- to large-scale CMPs or massively parallel multicores. Although C++ does not have concurrency constructs, C++ does have excellent support for many categories of library. So, you can add support for parallel programming and multithreading to C++ through the use of libraries. There are three very important C++ component libraries that support parallel programming that we introduce in this chapter: the Parallel STL Library (STAPL), Intel Thread Building Blocks (TBB), and the new C++0x standard. Although there are many different efforts that have generated concurrency support using C++, we introduce these three because they will be soon be the most widely available and easily accessible C++ components that support concurrency, parallel programming, and multithreading.

//Listing 8-1 An implementation of the new C++0x thread class.


  1  #ifndef BOOST_THREAD_THREAD_PTHREAD_HPP
  2  #define BOOST_THREAD_THREAD_PTHREAD_HPP
  3  // Copyright (C) 2001-2003
  4  // William E. Kempf
  5  // Copyright (C) 2007 Anthony Williams
  6  //
  7  //  Distributed under the Boost Software License,
     //  Version 1.0. (See accompanying
  8  //  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  9
 10  #include <boost/thread/detail/config.hpp>
 11
 12  #include <boost/utility.hpp>
 13  #include <boost/function.hpp>
 14  #include <boost/thread/mutex.hpp>
 15  #include <boost/thread/condition_variable.hpp>
 16  #include <list>
 17  #include <memory>
 18

19  #include <pthread.h>
 20  #include <boost/optional.hpp>
 21  #include <boost/thread/detail/move.hpp>
 22  #include <boost/shared_ptr.hpp>
 23  #include "thread_data.hpp"
 24  #include <stdlib.h>
 25
 26  #ifdef BOOST_MSVC
 27  #pragma warning(push)
 28  #pragma warning(disable:4251)
 29  #endif
 30
 31  namespace boost
 32  {
 33    class thread;
 34
 35    namespace detail
 36    {
 37        class thread_id;
 38    }
 39
 40    namespace this_thread
 41    {
 42        BOOST_THREAD_DECL detail::thread_id get_id();
 43    }
 44
 45    namespace detail
 46    {
 47        class thread_id
 48        {
 49        private:
 50            detail::thread_data_ptr thread_data;
 51
 52            thread_id(detail::thread_data_ptr thread_data_):
 53                thread_data(thread_data_)
 54            {}
 55            friend class boost::thread;
 56            friend thread_id this_thread::get_id();
 57        public:
 58            thread_id():
 59                thread_data()
 60            {}
 61
 62            bool operator==(const thread_id& y) const
 63            {
 64                return thread_data==y.thread_data;
 65            }
 66
 67            bool operator!=(const thread_id& y) const

68            {
 69                return thread_data!=y.thread_data;
 70            }
 71
 72            bool operator<(const thread_id& y) const
 73            {
 74                return thread_data<y.thread_data;
 75            }
 76
 77            bool operator>(const thread_id& y) const
 78            {
 79                return y.thread_data<thread_data;
 80            }
 81
 82            bool operator<=(const thread_id& y) const
 83            {
 84                return !(y.thread_data<thread_data);
 85            }
 86
 87            bool operator>=(const thread_id& y) const
 88            {
 89                return !(thread_data<y.thread_data);
 90            }
 91
 92            template<class charT, class traits>
 93            friend std::basic_ostream<charT, traits>&
 94            operator<<(std::basic_ostream<charT, traits>& os,
                          const thread_id& x)
 95            {
 96                if(x.thread_data)
 97                {
 98                    return os<<x.thread_data;
 99                }
100                else
101                {
102                    return os<<"{Not-any-thread}";
103                }
104            }
105        };
106    }
107
108    struct xtime;
109    class BOOST_THREAD_DECL thread
110    {
111    private:
112        thread(thread&);
113        thread& operator=(thread&);
114
115        template<typename F>
116        struct thread_data:
117            detail::thread_data_base
118        {
119            F f;
120

121            thread_data(F f_):
122                f(f_)
123            {}
124            thread_data(detail::thread_move_t<F> f_):
125                f(f_)
126            {}
127
128            void run()
129            {
130                f();
131            }
132        };
133
134        mutable boost::mutex thread_info_mutex;
135        detail::thread_data_ptr thread_info;
136
137        void start_thread();
138
139        explicit thread(detail::thread_data_ptr data);
140
141        detail::thread_data_ptr get_thread_info() const;
142
143    public:
144        thread();
145        ~thread();
146
147        template <class F>
148        explicit thread(F f):
149            thread_info(new thread_data<F>(f))
150        {
151            start_thread();
152        }
153        template <class F>
154        thread(detail::thread_move_t<F> f):
155            thread_info(new thread_data<F>(f))
156        {
157            start_thread();
158        }
159
160        thread(detail::thread_move_t<thread> x);
161        thread& operator=(detail::thread_move_t<thread> x);
162        operator detail::thread_move_t<thread>();
163        detail::thread_move_t<thread> move();
164
165        void swap(thread& x);
166
167        typedef detail::thread_id id;
168
169        id get_id() const;
170
171        bool joinable() const;
172        void join();
173        bool timed_join(const system_time& wait_until);

174
175        template<typename TimeDuration>
176        inline bool timed_join(TimeDuration const& rel_time)
177        {
178            return timed_join(get_system_time()+rel_time);
179        }
180        void detach();
181
182        static unsigned hardware_concurrency();
183
184        // backwards compatibility
185        bool operator==(const thread& other) const;
186        bool operator!=(const thread& other) const;
187
188        static void sleep(const system_time& xt);
189        static void yield();
190
191        // extensions
192        void interrupt();
193        bool interruption_requested() const;
194    };
195
196    inline detail::thread_move_t<thread> move(thread& x)
197    {
198        return x.move();
199    }
200
201    inline detail::thread_move_t<thread>
       move(detail::thread_move_t<thread> x)
202    {
203        return x;
204    }
205
206
207    template<typename F>
208    struct thread::thread_data<boost::reference_wrapper<F> >:
209        detail::thread_data_base
210    {
211        F& f;
212
213        thread_data(boost::reference_wrapper<F> f_):
214            f(f_)
215        {}
216
217        void run()
218        {
219            f();
220        }
221    };
222
223    namespace this_thread
224    {
225        class BOOST_THREAD_DECL disable_interruption

226        {
227            disable_interruption(const disable_interruption&);
228            disable_interruption& operator=(const disable_interruption&);
229
230            bool interruption_was_enabled;
231            friend class restore_interruption;
232        public:
233            disable_interruption();
234            ~disable_interruption();
235        };
236
237        class BOOST_THREAD_DECL restore_interruption
238        {
239            restore_interruption(const restore_interruption&);
240            restore_interruption& operator=(const restore_interruption&);
241        public:
242            explicit restore_interruption(disable_interruption& d);
243            ~restore_interruption();
244        };
245
246        BOOST_THREAD_DECL thread::id get_id();
247
248        BOOST_THREAD_DECL void interruption_point();
249        BOOST_THREAD_DECL bool interruption_enabled();
250        BOOST_THREAD_DECL bool interruption_requested();
251
252        inline void yield()
253        {
254            thread::yield();
255        }
256
257        template<typename TimeDuration>
258        inline void sleep(TimeDuration const& rel_time)
259        {
260            thread::sleep(get_system_time()+rel_time);
261        }
262    }
263
264    namespace detail
265    {
266        struct thread_exit_function_base
267        {
268            virtual ~thread_exit_function_base()
269            {}
270            virtual void operator()() const=0;
271        };
272
273        template<typename F>
274        struct thread_exit_function:
275            thread_exit_function_base
276        {
277            F f;

278
279            thread_exit_function(F f_):
280                f(f_)
281            {}
282
283            void operator()() const
284            {
285                f();
286            }
287        };
288
289        BOOST_THREAD_DECL void
           add_thread_exit_function(thread_exit_function_base*);
290    }
291
292    namespace this_thread
293    {
294        template<typename F>
295        inline void at_thread_exit(F f)
296        {
297            detail::thread_exit_function_base*
               const thread_exit_func=new detail::thread_exit_function<F>(f);
298            detail::add_thread_exit_function(thread_exit_func);
299        }
300    }
301
302    class BOOST_THREAD_DECL thread_group
303    {
304    public:
305        thread_group();
306        ~thread_group();
307
308        thread* create_thread(const function0<void>& threadfunc);
309        void add_thread(thread* thrd);
310        void remove_thread(thread* thrd);
311        void join_all();
312        void interrupt_all();
313        size_t size() const;
314
315    private:
316        thread_group(thread_group&);
317        void operator=(thread_group&);
318
319        std::list<thread*> m_threads;
320        mutex m_mutex;
321    };
322  } // namespace boost
323
324  #ifdef BOOST_MSVC
325  #pragma warning(pop)
326  #endif
327
328
329  #endif

//Listing 8-2 An implementation of the new standard C++0x mutex class.

  1  #ifndef BOOST_THREAD_PTHREAD_MUTEX_HPP
  2  #define BOOST_THREAD_PTHREAD_MUTEX_HPP
  3  // (C) Copyright 2007 Anthony Williams
  4  // Distributed under the Boost Software License, Version 1.0. (See
  5  // accompanying file LICENSE_1_0.txt or copy at
  6  // http://www.boost.org/LICENSE_1_0.txt)
  7
  8  #include <pthread.h>
  9  #include <boost/utility.hpp>
 10  #include <boost/thread/exceptions.hpp>
 11  #include <boost/thread/locks.hpp>
 12  #include <boost/thread/thread_time.hpp>
 13  #include <boost/assert.hpp>
 14  #ifndef WIN32
 15  #include <unistd.h>
 16  #endif
 17  #include <errno.h>
 18  #include "timespec.hpp"
 19  #include "pthread_mutex_scoped_lock.hpp"

20
 21  #ifdef _POSIX_TIMEOUTS
 22  #if _POSIX_TIMEOUTS >= 0
 23  #define BOOST_PTHREAD_HAS_TIMEDLOCK
 24  #endif
 25  #endif
 26
 27  namespace boost
 28  {
 29    class mutex:
 30        boost::noncopyable31    {
 32    private:
 33        pthread_mutex_t m;
 34    public:
 35        mutex()
 36        {
 37            int const res=pthread_mutex_init(&m,NULL);
 38            if(res)
 39            {
 40                throw thread_resource_error();
 41            }
 42        }
 43        ~mutex()
 44        {
 45            BOOST_VERIFY(!pthread_mutex_destroy(&m));
 46        }
 47
 48        void lock()
 49        {
 50            BOOST_VERIFY(!pthread_mutex_lock(&m));
 51        }
 52
 53        void unlock()
 54        {
 55            BOOST_VERIFY(!pthread_mutex_unlock(&m));
 56        }
 57
 58        bool try_lock()
 59        {
 60            int const res=pthread_mutex_trylock(&m);
 61            BOOST_ASSERT(!res || res==EBUSY);
 62            return !res;
 63        }
 64
 65        typedef pthread_mutex_t* native_handle_type;
 66        native_handle_type native_handle()
 67        {
 68            return &m;
 69        }
 70
 71        typedef unique_lock<mutex> scoped_lock;
 72        typedef scoped_lock scoped_try_lock;
 73    };

74
 75    typedef mutex try_mutex;
 76
 77    class timed_mutex:
 78        boost::noncopyable
 79    {
 80    private:
 81        pthread_mutex_t m;
 82  #ifndef BOOST_PTHREAD_HAS_TIMEDLOCK
 83        pthread_cond_t cond;
 84        bool is_locked;
 85  #endif
 86    public:
 87        timed_mutex()
 88        {
 89            int const res=pthread_mutex_init(&m,NULL);
 90            if(res)
 91            {
 92                throw thread_resource_error();
 93            }
 94  #ifndef BOOST_PTHREAD_HAS_TIMEDLOCK
 95            int const res2=pthread_cond_init(&cond,NULL);
 96            if(res2)
 97            {
 98                BOOST_VERIFY(!pthread_mutex_destroy(&m));
 99                throw thread_resource_error();
100            }
101            is_locked=false;
102  #endif
103        }
104        ~timed_mutex()
105        {
106            BOOST_VERIFY(!pthread_mutex_destroy(&m));
107  #ifndef BOOST_PTHREAD_HAS_TIMEDLOCK
108            BOOST_VERIFY(!pthread_cond_destroy(&cond));
109  #endif
110        }
111
112        template<typename TimeDuration>
113        bool timed_lock(TimeDuration const & relative_time)
114        {
115            return timed_lock(get_system_time()+relative_time);
116        }
117
118  #ifdef BOOST_PTHREAD_HAS_TIMEDLOCK
119        void lock()
120        {
121            BOOST_VERIFY(!pthread_mutex_lock(&m));
122        }
123

124        void unlock()
125        {
126            BOOST_VERIFY(!pthread_mutex_unlock(&m));
127        }
128
129        bool try_lock()
130        {
131            int const res=pthread_mutex_trylock(&m);
132            BOOST_ASSERT(!res || res==EBUSY);
133            return !res;
134        }
135        bool timed_lock(system_time const & abs_time)
136        {
137            struct timespec const timeout=detail::get_timespec(abs_time);
138            int const res=pthread_mutex_timedlock(&m,&timeout);
139            BOOST_ASSERT(!res || res==EBUSY);
140            return !res;
141        }
142  #else
143        void lock()
144        {
145            boost::pthread::pthread_mutex_scoped_lock const local_lock(&m);
146            while(is_locked)
147            {
148                BOOST_VERIFY(!pthread_cond_wait(&cond,&m));
149            }
150            is_locked=true;
151        }
152
153        void unlock()
154        {
155            boost::pthread::pthread_mutex_scoped_lock const local_lock(&m);
156            is_locked=false;
157            BOOST_VERIFY(!pthread_cond_signal(&cond));
158        }
159
160        bool try_lock()
161        {
162            boost::pthread::pthread_mutex_scoped_lock const local_lock(&m);
163            if(is_locked)
164            {
165                return false;
166            }
167            is_locked=true;
168            return true;
169        }
170
171        bool timed_lock(system_time const & abs_time)
172        {
173            struct timespec const timeout=detail::get_timespec(abs_time);
174            boost::pthread::pthread_mutex_scoped_lock const local_lock(&m);
175            while(is_locked)

176            {
177                int const cond_res=pthread_cond_timedwait(&cond,&m,&timeout);
178                if(cond_res==ETIMEDOUT)
179                {
180                    return false;
181                }
182                BOOST_ASSERT(!cond_res);
183            }
184            is_locked=true;
185            return true;
186        }
187  #endif
188
189        typedef unique_lock<timed_mutex> scoped_timed_lock;
190        typedef scoped_timed_lock scoped_try_lock;
191        typedef scoped_timed_lock scoped_lock;
192    };
193
194  }
195
196
197  #endif

Another important component that can be used in level 3 PADL analysis is the Intel Threading Building Blocks (TBB). The TBB is a set of C++ components consisting of generic algorithm templates, container classes, and Object-Oriented synchronization components, as well as other miscellaneous components that are very useful in multithreaded programming. The TBB is a runtime-based parallel programming model for C++ code that uses threads. It is designed primary to write scalable applications that:

Table 8-6 lists some of the primary template algorithms and containers that are available in the TBB library.

While the TBB intersects in a few areas (for example, mutexes), with the new concurrent programming library in the new C++ standard, it is largely complementary and provides a set of tools that can be used in the implementation Layer of PADL. Recall the seven steps from Figure 8-6. In Layer 4, we identified concurrency models. Layer 4 does not determine whether those concurrency models will be implemented by threads or processes. In fact, the concurrency models in Layer 4 can be implemented by clusters or other distributed computing models. The question and answer example that uses the Blackboard architecture does not indicate whether the knowledge sources should be implemented as threads or as processes. It also may be the case that one knowledge source may be implemented by a multiple threads or processes or even a combination of threads and processes. This can be necessary in order to meet the logical requirements of the knowledge source. To see how you might get to Layer 3 in the Blackboard example, you can take a closer look at the control strategies in the Blackboard architecture.

//Listing 8-3 A Program that uses concurrent_vector and parallel_for from TBB.

  1  using namespace std;
  2  #include <iostream>
  3  #include <vector>
  4  #include <stdlib.h>
  5  #include <ctype.h>
  6  #include <algorithm>
  7  #include <iterator>
  8  #include <string>
  9  #include "tbb/blocked_range.h"
 10  #include "tbb/parallel_for.h"
 11  #include "tbb/task_scheduler_init.h"
 12  #include "tbb/concurrent_vector.h"
 13  #include <sstream>
 14  #include <fstream>
 15
 16  using namespace tbb;
 17  concurrent_vector<string>  Terms;
 18  concurrent_vector<string>  Question;
 19
 20
 21  class lower_case{
 22
 23  public:
 24     char operator()(char X){
 25
 26        return(tolower(X));
 27     }
 28
 29  };
 30
 31
 32
 33  void changeIt(string &X)
 34  {
 35     transform(X.begin(),X.end(),X.begin(),lower_case());
 36  }

37
 38
 39
 40  void tokenize(string &X)
 41  {
 42     stringstream Sin(X);
 43     string Token;
 44     while(!Sin.fail() && Sin.good())
 45     {
 46        Sin >> Token;
 47        Terms.push_back(Token);
 48     }
 49  }
 50
 51
 52  class parallel_lower_case{
 53
 54  public:
 55
 56     void operator() (const blocked_range<int> &X) const
 57     {
 58        for(int I = X.begin(); I != X.end(); I++)
 59        {
 60
 61           changeIt(Terms[I]);
 62
 63         }
 64
 65     }
 66
 67  };
 68
 69  class valid_tokens{
 70  public:
 71     void operator() (const blocked_range<int> &X) const
 72     {
 73        for(int I = X.begin(); I != X.end(); I++)
 74        {
 75           tokenize(Question[I]);
 76
 77        }
 78
 79     }
 80
 81  };
 82
 83
 84
 85
 86  int main(int argc,char *argv[])
 87  {
 88
 89    task_scheduler_init Init;
 90    ifstream Fin("question.txt");

91    istream_iterator<string> Ftr(Fin);
 92    istream_iterator<string> Eof;
 93    copy(Ftr,Eof,back_inserter(Question));
 94    Fin.close();
 95    parallel_lower_case Lower;
 96    valid_tokens  Token;
 97    parallel_for(blocked_range<int>(0,Question.size(),
                                      (Question.size() /2)),Token);
 98    parallel_for(blocked_range<int>(0,Terms.size(),
                                      (Terms.size() /2)),Lower);
 99    ostream_iterator<string> Out(cout,"
");
100    copy(Terms.begin(),Terms.end(),Out);
101
102
103  }

As noted, concurrent programming library facilities will appear in the new C++ standard, including a long awaited thread library and synchronization components. However, another important set of C++ components that will support parallel programming is the Standard Template Adaptive Parallel Library (STAPL). Whereas TBB and the upcoming concurrent programming library in C++ are designed to work with multicore and parallel computers, STAPL is designed to work on both shared and distributed memory parallel computers. The STAPL library design goals are consistent with our PADL analysis approach to designing parallel programs. STAPL is designed to allow developers to work at a high level of abstraction. It provides interface classes and interface algorithms that hide many of the details specific to parallel programming. Throughout this book, we have made a distinction between application-level developers and system-level developers. System-level development tends to work closer to the operating system APIs and SPIs. STAPL users are divided into three groups:

Bjarne Stroustrup, the inventor of C++, is involved with the development of STAPL. This means that you can count on STAPL to be consistent with the philosophy of the C++ standard. STAPL consists of these primary components:

Figure 8-7 shows a block diagram of the structure of the STAPL library.

Figure 8.7. Figure 8-7

The standard C++ concurrent programming library will be complementary and compatible with STAPL.

The TBB is in part inspired by design concepts in STAPL, but STAPL is a higher-level framework that extends both the STL and TBB. Also notice in Figure 8-7 that the Runtime system can and will interface with the POSIX pthread API as well as with other operating thread and process APIs. You can see from looking at the structures of the new concurrent programming class library that will be part of C++0x, TBB, and STAPL that using interface classes and components that wrap lower-level operating system primitives is the most practical way to provide concurrency support to the C++ developer. Notice in Figure 8-7 that the user application code is at least two layers above the POSIX threads. If you look back at Figure 4-1 in Chapter 4, it shows the relationships for the developer's view of the operating system and frameworks such as STAPL. The complexity and special challenges of parallel programming as discussed in Chapter 3 require that the software developer have a clear understanding of the integration between class libraries, application frameworks, pattern classes, algorithm templates, and the concurrency and synchronization services that the operating system provides. PADL and PBS analysis (which is discussed later in the chapter) are performed in the context of a solid understanding of the relationships of all of the pieces involved.

The new standard C++ concurrent programming class libraries, TBB, and STAPL provide the bulk of the implementation domain independent components that you need in Layer 3 of the PADL analysis. Keep in mind that Layer 3 components consist of domain-specific application frameworks, class libraries, and so forth as well as domain-independent components.

If you look at the Blackboard example, the segmentation of the Blackboard into parts determines whether CREW or CRCW concurrency (determined in Layer 2 of PADL) is appropriate. The most flexible model of critical section access is CRCW. CRCW can be achieved depending on the structure of the Blackboard. For instance, if 16 knowledge sources are involved in a collaborative effort and each knowledge source accesses its own segment of the Blackboard, then these knowledge sources can concurrently read and write the Blackboard without data race problems. Looking at the communication model can also help determine what Layer 3 components will be used. Obviously, containers that support concurrency such as the TBB concurrent_vector<T> or concurrent_queue<T> or pContainers from STAPL can be used to implement some portions of the Blackboard that require CREW. With a little planning, these structures can also support CRCW.

One of the major reasons that we choose multiagent architectures and Blackboard architectures as our two fundamental application architectures for Layer 5 in PADL is that the patterns of work that can be captured by these architectures are extremely flexible and well understood. Here is an important point.

Before putting effort into the coordination and synchronization of concurrent threads or processes in your application, it is better to have a solid handle on the pattern of work at the domain and application level.

STAPL supports work at a higher level. The TBB is best used when the developer thinks in terms of tasks not threads. Here, we go a step further; think about the "story" of your application, how the actors and objects naturally interface. Work out the pattern of work at the model level in Layers 4 and 5. Understand the parallelism or concurrency in terms of a well-known architecture that supports concurrency (for example, Blackboards, multiagents).

To examine this further, take a closer look closer at the Blackboard control strategy for the example used in this chapter.

The layer of control in a Blackboard involves the selection of which knowledge sources to involve in the search for the solution and which aspects of the problem to focus on. This is a focus or attention layer. This layer of control focuses on a certain area of the problem and selects knowledge sources accordingly. Major issues to tackle in any kind of problem solving are where to start and what kind of information is needed to solve the problem. The focus/attention layer evaluates the initial conditions of the problem and then controls which knowledge sources to use and where they start. The available knowledge sources are known to the Blackboard, and typically the knowledge source accepts messages or parameters that dictate how it should proceed or where in the solution space it should begin the search. For parallel implementations, this layer determines the basic concurrency model for Layer 4 in PADL. Usually for Blackboards, this is the Multiple Programs Multiple Data (MPMD — a.k.a. MIMD) model because each knowledge source/problem solver has its own area of specialty. However, the nature of the problem might warrant the popular Single Program Multiple Data (SPMD or SIMD) model. If this model is used, the control layer spawns N number of the same knowledge source but pass different parameters to each.

The next layer of control involves determining what to do with the solution or partial solutions that are written to the Blackboard. This layer of control will determine whether the knowledge sources can stop work or whether the solution that was generated is acceptable, unacceptable, partially acceptable, and so on. This layer of control has complete visibility of the Blackboard and all the partial or tentative solutions. It guides the overall problem-solving strategies of the collective. As with the layout of the Blackboard and the structure of the knowledge sources, the Blackboard model suggests the existence of a control component but does not specify how it should be structured. Sometimes the control component is part of the Blackboard. Sometimes the control component is implemented by the knowledge sources. In some cases, the control component is implemented by modules external to the Blackboard. The control component can also be implemented by any combination of these. The knowledge sources collectively search for a solution to some problem. We want to emphasize a solution because many problems have more than one solution. Some of the solutions may be deeper in the search space than others. Some solutions may cost more to find than others. Some solutions may be deemed not good enough. The control component helps to manage the collective search strategies of the knowledge sources. The control component monitors the tentative or partial solutions to make sure that the knowledge sources are not pursuing an impractical search strategy. The control component looks out for any infinite loops, blind alleys, or recursive regression. Further, the control component is involved in selecting the best or the most appropriate knowledge sources for the problem. As the knowledge sources make progress toward a solution, the control component may relieve some knowledge sources while assigning others. The control strategy will be closely related to the search strategies used by the knowledge sources. It is important to remember that the knowledge sources may each use different search strategies and problem-solving techniques. Although they work with a common Blackboard, the knowledge sources or problem solvers are essentially autonomous and self-contained. Therefore, this layer of control has a two-way communication with the knowledge sources. Figure 8-8 shows possible control configurations and their layers in a Blackboard architecture.

Figure 8.8. Figure 8-8

Notice the relationships between the Blackboard and the knowledge sources in Figure 8-8. If this interface is properly and completely worked out at the design level, then mapping knowledge sources or agents to tasks, threads, or processes is easier. It is not practical to attempt to optimize threads or processes and coordinate communication or synchronization at the implementation level if things are murky at the design and domain level. On the other hand, if all of the relationships are completely clear at the design level, if the patterns of work are well understood, and if the details of actor/object interaction have been worked out, then mapping to threads or processes is straightforward.

The chances for a successful software deployment are greatly increased. The "story" of the application, that is, its beginning, middle, and ending, has to be clear to all the developers involved. This understanding starts with a PADL analysis and PBS of your software application.