wiki:Traffic:

Version 18 (modified by stefan.nour, 14 years ago) (diff)

--

Acronimul Proiectului: Numele proiectului

  • Membri echipei: Stefan Nour - stefan.nour, Raluca Negru - raluca.negru;
  • Descriere proiect: Improving the algorithm for computing the shortest path to a destination for graphs with large numbers of nodes and integrate it in an existing framework for traffic rerouting.

Related Work

We recently discovered a new way of parallelizing a program in Java by using Parallel Java( an API and middleware for parallel programming in 100% Java on shared memory multiprocessor (SMP) parallel computers, cluster parallel computers, and hybrid SMP cluster parallel computers). All the files related to this project are on the SVN and at the bottom of this page as attachments.

We tried to simulate the test performed by them but we did not obtain the same results. The main issue that we discussed about at our presentation (the time of execution for the parallel implementation on 1 thread vs. the time of execution of the sequential algorithm) was proven to be wrong for them. As our test confirmed, the sequential algorithm runs a little bit faster.

The sequential algorithm on 1 thread:

[0] -> [23] -> [51] -> [99] (Total Distance = 7)
Running Time : 407

The parallel algorithm on 1 thread:

[0] -> [23] -> [51] -> [99] (Total Distance = 7)
Running Time : 428

Implementation

We tried to integrate the parallelized algorithm into the existing framework by calling a C program from a java context. Figure below illustrates the process for using JDK or Java 2 SDK releases to write a simple Java application that calls a C function to print "Hello World!". The process consists of the following steps:

  1. Create a class (HelloWorld?.java) that declares the native method.
  2. Use javac to compile the HelloWorld? source file, resulting in the class file HelloWorld?.class. The javac compiler is supplied with JDK or Java 2 SDK releases.
  3. Use javah -jni to generate a C header file (HelloWorld?.h) containing the function prototype for the native method implementation. The javah tool is provided with JDK or Java 2 SDK releases.
  4. Write the C implementation (HelloWorld?.c) of the native method.
  5. Compile the C implementation into a native library, creating Hello-World.dll . Use the C compiler and linker available on the host environment.
  6. Run the HelloWorld? program using the java runtime interpreter. Both the class file (HelloWorld?.class) and the native library (HelloWorld?.dll) are loaded at runtime.

Here is an example of how this works:

Declare the Native Method

You begin by writing the following program in the Java programming language. The program defines a class named HelloWorld? that contains a native method, print.

class HelloWorld? {

private native void print(); public static void main(String[] args) {

new HelloWorld?().print();

} static {

System.loadLibrary("HelloWorld?");

}

}

The HelloWorld? class definition begins with the declaration of the print native method. This is followed by a main method that instantiates the Hello-World class and invokes the print native method for this instance. The last part of the class definition is a static initializer that loads the native library containing the implementation of the print native method.

There are two differences between the declaration of a native method such as print and the declaration of regular methods in the Java programming language. A native method declaration must contain the native modifier. The native modifier indicates that this method is implemented in another language. Also, the native method declaration is terminated with a semicolon, the statement terminator symbol, because there is no implementation for native methods in the class itself. We will implement the print method in a separate C file.

Before the native method print can be called, the native library that implements print must be loaded. In this case, we load the native library in the static initializer of the HelloWorld? class. The Java virtual machine automatically runs the static initializer before invoking any methods in the HelloWorld? class, thus ensuring that the native library is loaded before the print native method is called.

We define a main method to be able to run the HelloWorld? class. Hello-World.main calls the native method print in the same manner as it would call a regular method.

System.loadLibrary takes a library name, locates a native library that corresponds to that name, and loads the native library into the application. We will discuss the exact loading process later in the book. For now simply remember that in order for System.loadLibrary("HelloWorld?") to succeed, we need to create a native library called HelloWorld?.dll on Win32.

Compile the HelloWorld? Class

After you have defined the HelloWorld? class, save the source code in a file called HelloWorld?.java. Then compile the source file using the javac compiler that comes with the JDK or Java 2 SDK release:

javac HelloWorld?.java

This command will generate a HelloWorld?.class file in the current directory.

Create the Native Method Header File

Next we will use the javah tool to generate a JNI-style header file that is useful when implementing the native method in C. You can run javah on the Hello-World class as follows:

javah -jni HelloWorld?

The name of the header file is the class name with a ".h" appended to the end of it. The command shown above generates a file named HelloWorld?.h. We will not list the generated header file in its entirety here. The most important part of the header file is the function prototype for Java_HelloWorld_print, which is the C function that implements the HelloWorld?.print method:

JNIEXPORT void JNICALL Java_HelloWorld_print (JNIEnv *, jobject);

Ignore the JNIEXPORT and JNICALL macros for now. You may have noticed that the C implementation of the native method accepts two arguments even though the corresponding declaration of the native method accepts no arguments. The first argument for every native method implementation is a JNIEnv interface pointer. The second argument is a reference to the HelloWorld? object itself (sort of like the "this" pointer in C++).

Write the Native Method Implementation

The JNI-style header file generated by javah helps you to write C or C++ implementations for the native method. The function that you write must follow the -prototype specified in the generated header file. You can implement the Hello-World.print method in a C file HelloWorld?.c as follows:

#include <jni.h> #include <stdio.h> #include "HelloWorld?.h"

JNIEXPORT void JNICALL Java_HelloWorld_print(JNIEnv *env, jobject obj) {

printf("Hello World!\n"); return;

}

The implementation of this native method is straightforward. It uses the printf function to display the string "Hello World!" and then returns. As mentioned before, both arguments, the JNIEnv pointer and the reference to the object, are ignored.

The C program includes three header files:

  • jni.h -- This header file provides information the native code needs to call JNI functions. When writing native methods, you must always include this file in your C or C++ source files.
  • stdio.h -- The code snippet above also includes stdio.h because it uses the printf function.
  • HelloWorld?.h -- The header file that you generated using javah. It includes the C/C++ prototype for the Java_HelloWorld_print function.

Compile the C Source and Create a Native Library

Remember that when you created the HelloWorld? class in the HelloWorld?.java file, you included a line of code that loaded a native library into the program:

System.loadLibrary("HelloWorld?");

Now that all the necessary C code is written, you need to compile Hello-World.c and build this native library.

Different operating systems support different ways to build native libraries. On Win32, the following command builds a dynamic link library (DLL) HelloWorld?.dll using the Microsoft Visual C++ compiler:

cl -Ic:\java\include -Ic:\java\include\win32

-MD -LD HelloWorld?.c -FeHelloWorld?.dll

The -MD option ensures that HelloWorld?.dll is linked with the Win32 multithreaded C library. The -LD option instructs the C compiler to generate a DLL instead of a regular Win32 executable. Of course, on both Solaris and Win32 you need to put in the include paths that reflect the setup on your own machine.

Run the Program

At this point, you have the two components ready to run the program. The class file (HelloWorld?.class) calls a native method, and the native library (Hello-World.dll) implements the native method.

Because the HelloWorld? class contains its own main method, you can run the program on Solaris or Win32 as follows:

java HelloWorld?

You should see the following output:

Hello World!

It is important to set your native library path correctly for your program to run. The native library path is a list of directories that the Java virtual machine searches when loading native libraries. If you do not have a native library path set up correctly, then you see an error similar to the following:

java.lang.UnsatisfiedLinkError?: no HelloWorld? in library path

at java.lang.Runtime.loadLibrary(Runtime.java)
at java.lang.System.loadLibrary(System.java)
at HelloWorld?.main(HelloWorld?.java)

Make sure that the native library resides in one of the directories in the native library path. If you are running on a Windows 95 or Windows NT machine, make sure that HelloWorld?.dll is in the current directory, or in a directory that is listed in the PATH environment variable.

In Java 2 SDK 1.2 release, you can also specify the native library path on the java command line as a system property as follows:

java -Djava.library.path=. HelloWorld?

The "-D" command-line option sets a Java platform system property. Setting the java.library.path property to "." instructs the Java virtual machine to search for native libraries in the current directory.

Experimental Results

The results were obtained for a 1000 nodes graph using the Dijkstra algorithm parallelized with OpenMp? on specified number of threads on cluster.

Attachments (3)

Download all attachments as: .zip