News on FGCS Technology and related activities by the Research Institute
for Advanced Information Technology (AITEC), the successor to ICOT
JIPDEC AITEC News
September 13, 1996 Issue #5
[Table of Contents]
Let's join the world of KL1, a general purpose parallel logic programming
language!
AITEC NEWS Issue#5 deals solely with issues concerning the First KLIC
PROGRAMMING CONTEST in 1996.
AITEC decided to hold the first KLIC Programming Contest in this fall. This
is a very good chance for you to learn or evaluate your programming skills
using KL1 with KLIC. After review by the evaluation committee, the
outstanding and interesting programs will receive awards, with attractive
prizes also to give away.
Today, parallel machines are often used for general use in business systems
such as database servers. They are sometimes called "data warehouses," as
they are used for purposes other than their former purpose of performing
scientific calculations.
We believe that KL1, as a programming language for programming parallel
machines for business use, offers tremendous advantages in generality and
productivity compared to any other parallel language. If you use KL1 with
KLIC, you can run KL1 programs on UNIX-based machines and easily make them
linked with other programs written in C or other programming languages.
The KLIC Programming Contest is open to anyone who wishes to enter. New and
novice KL1 users are especially welcome. We will be giving away a KLIC
tutorial text book to all who enter, and KLIC seminars will be held for
domestic applicants.
Please read the following "How to enter" first, then fill out the Entry
form and mail it to us as soon as possible to let us know you intend to
participate in the contest. Then please start writing your program(s)
according to "Programming Subject" and mail it to us before the deadline,
November 5.
If you don't have a KLIC system, you can get the system and its manual from:
http://www.icot.or.jp/ICOT/IFS/IFS-abst/085.html
/ifs/symbolic-proc/unix/klic/klic.tgz
We look forward to receiving your entry!
The KLIC Programming Contest in 1996 is hosted by the Research Institute
for Advanced Information Technology (AITEC) of the Japan Information
Processing Development Center (JIPDEC), and is organized by the KLIC
Programming Contest Executive Committee.
KLIC Programming Contest Executive Committee:
Fumio Mizoguchi, Prof., Tokyo Science University (Chairman)
Kazunori Ueda, Assistant Prof, Waseda University
Jiro Tanaka, Assistant Prof., Tsukuba University
Takashi Chikayama, Assistant Prof., University of Tokyo
Keiji Hirata, Principal Researcher, NTT
Akira Aiba, Principal Researcher, AITEC
The KLIC Programming Contest is open to anyone who wishes to enter.
We will be giving away a KLIC tutorial text book to all who enter.
2.1 Programming Categories
===========================
We are soliciting programs written in KL1 in the following three categories:
Category 1. Programs for the given subject in a sequential environment
Category 2. Programs for the given subject in a parallel environment
Category 3. Programs on any subject
You can program free subjects either in a sequential or in a parallel
environment.
2.2 Important Dates
====================
Deadline for Entry: October 14(Mon), 1996
Deadline for Application: November 5(Tue), 1996
Awards Announcement Date: November 29 (Fri), 1996
Ceremony of Award Honors: Early in December, 1996
(The ceremony is only for domestic applicants.)
KLIC Seminar Schedule for Domestic Applicants: October 4 (Fri), 1996
Participation in the KLIC Seminars: If you wish to participate in the KLIC
seminar, please send mail to klic-contest@icot.or.jp.
2.3 Awards Announcement
=======================
The submitted programs will be reviewed by the evaluation committee of this
contest according to its selection standards, and 1st and 2nd prizes and
honorable mentions will be chosen in each category. We will award for each
prize as follows;
1st prize (supplementary prize: 500,000 yen)
2nd prize (supplementary prize: 300,000 yen)
Honorable mention (supplementary prize: 100,000 yen)
The winning programs will be introduced on the AITEC Home Page.
Participation prizes will be given to those applications which pass
screening by the evaluation committee.
Participation prize (book coupon worth 5,000 yen)
Screening: The programs submitted both for the sequential and the parallel
environment will be checked to see whether they run properly and whether
they produce the correct solutions within a certain time. The programs in
the free subject category will be checked according to the standards set by
the evaluation committee.
The results will be sent to all applicants via email by November 29, and
will also be announced on the AITEC Home Page and in some magazines. We
will hold the awards ceremony at AITEC early in December.
2.4 Copyrights
================
The copyright for submitted programs shall belong to the applicants. For
the winning programs, however, please note that AITEC reserves the right to
use them without payment for publicity purposes.
2.5 How to Enter?
========================
We can accept entries for the contest by email only. Please fill out the
following items and send mail to the following address with the subject
name "ENTRY."
Mail address: klic-contest@icot.or.jp
Subject name: ENTRY
Please include the following information in your entry form:
Name : If you apply in a group, please write the leader's name first,
followed by all the members' names.
Affiliation : If you apply in a group, please write the leader's affiliation.
Email Address: If you apply in a group, please write all the members'
Internet addresses.
Phone Number : If you apply in a group, please write the leader's number.
Entry Category:You can apply for more than one of the above categories.
If you submit more than one program, you must specify the
category for each. If you have not decided the category yet,
please write "undecided."
To those who enter, we will send you a return email.
You can also enter from the AITEC Home Page.
3.1 What is "multiset?"
=======================
Please read the following explanation on the notion of "multisets" first.
A radio network recently offered several giveaway packages to its
listeners. Each of the packages attracted much interest, and some people
applied for more than one package.
To pigeonhole the applications, they asked applicants to write down their
contact telephone number. Let us assume that an applicant is identified by
this telephone number. If more than one person from the same family applies
for the same package or one person applies more than once using the names
of family members, then all the applications are assumed to be from the
same person, but we decided to ignore this.
Lists of applicants are primarily used when drawing lots, but in addition,
information on who wanted what are of great value when deciding prizes in
future giveaway packages and, more importantly, for marketing purposes.
For ease of explanation, we'll assume that telephone numbers consist of
only one digit in the following.
Assume, for example, that package A is applied for by those with telephone
numbers 7, 1, 2, 7, and 7. Here, the one with number 7 applied three times
for the same package.
Those who applied for package B had numbers 5, 7, 2, and 7.
The applicants can be represented by two multisets: A = {7,1,2,7,7} and
B = {5,7,2,7}. With multisets, the order of elements is not significant.
Thus, all {7,1,2,7,7}, {2,1,7,7,7}, and {7,2,7,1,7} mean the same multiset A.
By applying operations to multisets, we can obtain various information. The
following shows several operations and their examples.
Union: Packages A and B are different packages but some drawing lots should
be made in common. We need a joint list of those who applied for both
of the packages. With the above values of two multisets, the union
operation is as follows.
{7,1,2,7,7}\cup{5,7,2,7}={7,7,2,7,7,5,1,7,2}
Contraction: For some drawing lots, multiple applications from one person
should be regarded as a single application. The contraction operation,
denoted by |{}|, removes all the duplicated elements as follows.
|{7,1,2,7,7}| = {2,1,7}
|{5,7,2,7}| ={5,7,2}
Intersection: We'd like to know who applied for both packages A and B. If
one applies multiple times to both, we also want to know this. This
information can be obtained by computing the intersection that
enumerates common elements of two multisets, as follows:
{7,1,2,7,7}\cap{5,7,2,7}= {7,2,7}
Difference: We'd like to know who prefers one product to another and how
strongly. A guess is made by knowing who applied for package A more
times than for package B. The following difference operation fulfills
this need.
{7,1,2,7,7}\{5,7,2,7}= {7,1}
{5,7,2,7}\{7,1,2,7,7}= {5}
3.2 These are the problems you should solve.
===========================================
Now comes the main body of the problem.
Write a program module multi_set that has the following seven predicates:
1. A predicate that converts a multiset given as a list L into some
appropriate internal representation M: encode(L, M)
2. A predicate that converts internal representation M back to list
representation L: decode(M, L)
3. A predicate that computes the union of two multisets in internal
representation M0 and M1, M0 \cup M1, into M: union(M0, M1, M)
4. A predicate that computes the intersection of two multisets in internal
representation M0 and M1, M0 \cap M1, into M: intersection(M0, M1, M)
5. A predicate that computes the difference of two multisets in internal
representation M0 and M1, M0 \ M1, into M: difference(M0, M1, M)
6. A predicate that removes duplicated elements of a multiset in internal
representation M0 to M, M = |M0|,: contraction(M0, M)
7. A predicate that chooses one arbitrary element from a multiset in
internal representation M, and returns the element E and the rest of the
multiset S, M = {E} \cup S: choose(M, E, S)
Cases when M is an empty multiset may be neglected.
3.3 Your program(s) will be checked as follows:
================================================
Programs are examined by calling the predicates 1 through 7 from testing
programs provided by AITEC.
The testing programs give multiset data as a list of integer numbers
possibly with duplicates.
In this contest, the elements of multisets are restricted to integer
numbers. Applicants' programs may convert data in list format to their own
format for various operations. The final answer will be converted back to
the list format.
To give an idea of the examination method, a sample test program is
enclosed in this document. Note that this is not the program used in the
official examination.
The size of the data will be considerably large. The handling data of
invalid format need not be considered. For example, the encoding predicate
can assume that the input is a list of integers and other predicates can
assume that all the input parameters are the results of encoding or other
operations performed by the program itself.
Our interest in concurrent and parallel programming is in realizing
programs that can handle a variety of input data on a variety of
architecture elegantly and efficiently. Please keep such variety in mind
when constructing your program.
No single criteria is sufficient for estimating concurrent and parallel
programs. Please bear in mind that the examination process includes reading
the source code through.
Please do not forget to attach documents describing why you thought the way
you programmed it was appropriate.
3.4 An example of the checking program
======================================
To give an idea of the examination, a sample test program is enclosed in
this document. Note that this is not the program used in the official
examination.
----------------------------------------------------------------------------
:- main module
main:-
go1(A1),
go2(A2),
klicio:klicio([stdout(NS)]),
( NS = normal(S) -> S = [putt(A1),nl,putt(A2),nl]).
go1(L):-
gen_3_ms(L0,L1,L2), % 3 multi sets generated by random numbers
multi_set:encode(L0,M0),
multi_set:encode(L1,M1),
multi_set:encode(L2,M2),
% symmetrical set operations done at the following 6 lines
multi_set:intersection(M0,M1,M0i),
multi_set:intersection(M1,M2,M1i),
multi_set:intersection(M2,M0,M2i),
multi_set:difference(M0i,M1i,Md0),
multi_set:difference(M1i,M2i,Md1),
multi_set:difference(M2i,M0i,Md2),
multi_set:contraction(Md2,Mc), % a slightly irregular operation
multi_set:union(Md0,Md1,M01),
multi_set:union(M01,Mc,Mu),
multi_set:decode(Mu,L).
go2(L):-
gen_ms(13,11,S), % a multi set such that the max value of elements = 13
% and the num of elements = 11
multi_set:encode(S,T),
pset(T,P),
multi_set:decode(P,L).
pset(S,P):- % calculate the power set of a multi set S
multi_set:decode(S,D),
( D = [] -> multi_set:encode([],E),
multi_set:encode([E],P)
;
D \= [] -> multi_set:choose(S,C,S1), % split an element C and the others S1
pset(S1,P1),
multi_set:encode([C],Cs),
map_union(P1,Cs,P2),
% the power set of S constructed
% by P1 (the power set S1) and C
multi_set:union(P1,P2,P) ).
map_union(S,X,Y):-
multi_set:decode(S,D), % add X to each element of multi set S
( D = [] -> multi_set:encode([],Y)
;
D \= [] -> multi_set:choose(S,C,S1),
multi_set:union(C,X,CX),
% at this line, make the union of X and each element
multi_set:encode([CX],Z),
% making answer multi set Y from the union of Z and S2
multi_set:union(Z,S2,Y),
map_union(S1,X,S2) ).
gen_3_ms(L0,L1,L2):-
gen_ms_list(97,~(2 << 6 - 1),3,L),
% in the official examination, different parameters will be used
( L = [M0,M1,M2] -> M0 = L0, M1 = L1, M2 = L2 ).
% decompose a list and pick up elements
/*
* create a list, each element of which is a multi set (the max value of
* its elements is Max, the number of its elements is Card) and the length
* is ListLen
*/
gen_ms_list(Max,Card,ListLen,MSs):- true |
generic:new(random_numbers)+RDM+97,
gen_ms_list_0(Max,Card,ListLen,MSs)-RDM.
gen_ms_list_0(Max,Card,ListLen,MSs)-RDM:- ListLen =:= 0 |
MSs = [].
gen_ms_list_0(Max,Card,ListLen,MSs)-RDM:- ListLen >= 1 |
gen_ms(Max,Card,MS)-RDM,
MSs = [MS|N],
gen_ms_list_0(Max,Card,~(ListLen-1),N)-RDM.
/* create a multi set, the max value of its elements is Max and the number
of its elements is Card */
gen_ms(Max,Card,MS):-
generic:new(random_numbers)+RDM+91,
gen_ms(Max,Card,MS)-RDM.
gen_ms(Max,Card,MS)-RDM:- Card =:= 0 |
MS = [].
gen_ms(Max,Card,MS)-RDM:- Card >= 1 |
RDM <= Random, % generate a random number on demand
MS = [~(Random mod Max)|N],
gen_ms(Max,~(Card-1),N)-RDM.
4.1 Details of how to organize your program and document.
=========================================================
Your program and document should be sent to us by email no later than
November 5.
The email message should be organized as follows:
(1) The destination address should be "klic-contest@icot.or.jp".
(2) The Subject of the email should be "KLIC Contest."
(3) The body of the email should include the following information:
a. Please specify "Application for KLIC Programming Contest" as the title
at the top.
b. Your name*
c. Your affiliation*
d. Your address*
e. Your telephone number*
f. Your email address*
g. Please specify the category you are applying for, namely, the
sequential environment, parallel environment, or free subject.
(* If you apply as a group, please specify the leader's name, affiliation,
telephone number and email address.)
In the body of the email, after these seven items, please put the files
specified below into one directory and compress it by "tar", "gzip (or
compress)" or "uuencode."
1) Explanation or Manual of your program
Please write explanatory documents or manuals for your program either in
Japanese or English. They should be saved as plain text or in HTML. Please
name the file "README" or "README.html".
If you need to use figures or pictures, please convert them into the "gif"
format and put them into a subdirectory named "readme.dir".
If you use links in HTML documents, their references should be directed to
the files in the directory "readme.dir." The version of HTML should be 2.0
or newer.
If you apply to the free subject category, you are requested to describe
also the following items:
a. Name of the program
b. General explanation of its function, behavior and so on
c. Rough elapsed time to generate the answer(s) using the test data you
attach with it.
2) Make a list of all the source file names and put it in a file named
"SOURCES".
Please write one source file name per line. For example, if you have two
source files, foo.kl1 and bar.kl1, then your "SOURCES" file should contain
two lines as follows:
foo.kl1
bar.kl1
(note)
If your program cannot be installed by the command "klic *.kl1" for linking
some libraries, for example, please arrange a file such as "makefile" which
can generate an executable object file. In this case, please add a document
regarding the installation procedure to the item 3) described below with
the name "compile.doc".
3) Source program files
You may divide your source program into as many files as you need. If you
apply to the free subject category and have some test data, please name the
file "test.data" and include it with these files.
4.2 About the environment(s) to run your program
=================================================
1) Sequential environment
A UNIX workstation:
On execution, option -H4M is specified to give the maximum heap size.
The OS is SUN OS 4.1.3.
2) Parallel environment
A SparcCenter 2000:
SuperSparc 40MHz x 20, secondary cache is 1MB.
Main memory is 1311 MB.
Maximum number of worker processes will be 16.
The OS is Solaris 2.3.
Do you understand the problems you have to program? Or have you already
finished programming?
A few years ago when we were preparing to close the ICOT and thinking about
how to continue promoting FGCS technology, we expected that within a few
years Unix-based parallel machines would be popular and widely available
for engineers, programmers, and graduate students as well as researchers.
However, the reality is different, and the machines are still too
expensive. Researchers cannot use them freely and easily, for instance, to
solve the problems given above.
If you want to write an efficient parallel program in KL1 or any other
parallel language, you need a parallel machine and a programming
environment where you can try out performance tuning for your program.
Recognizing this situation, we decided to hold this KL1 Programming Contest
by preparing the sequential environment category for KL1 programming.
We believe that if you learn KL1 programming even in a sequential
environment, then you can easily build real parallel programs when you get
to work a parallel machine and a parallel programming environment. Parallel
programming includes a new culture which is, in some sense, different from
traditional sequential programming. We hope that you can enjoy even just a
part of this culture and can win an award.
We look forward to receiving your entry!
**********************************************************************
* *
* A I T E C N E W S Issue #5 *
* AITEC NEWS Editorial Team: *
* Makiko Sato, Chie Takahashi, Akira Aiba *
* Hiroshi Sato, Shunichi Uchida *
* Issued: August , 1996 *
* By: Research Institute for Advanced Information *
* Technology (AITEC), a subcenter of *
* Japan Information Processing Development *
* Center (JIPDEC) *
* 2-3-3, Minato-ku, Shiba, Tokyo 105, Japan *
* Tel: 03-3456-3191 Fax: 03-3455-4877 *
* E-mail: aitec-news@icot.or.jp *
* *
**********************************************************************