Paper Abstract and Keywords |
Presentation |
2009-03-02 16:15
A division technique for a SAT problem in a distributed SAT solver Akihide Takami, Hidetomo Nabeshima, Koji Iwanuma (Yamanashi Univ) SS2008-52 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
In this paper, we introduce SatCube which is a Boolean satisfiability (SAT) problem solver and is a parallel and distributed
system. A SAT problem is a fundamental problem in computer science and has many application areas such as planning, schedul
ing and hardware verification. SatCube is based on MiniSat which is one of the fastest serial SAT solver in the world. In or
der to solve SAT problem efficiently, SatCube divide the SAT problem into sub-problems by three kinds of ways: (1) exhaustive division, (2) exhaustive division with multiple search strategies and (3) random division, and shares learnt clauses with
every slave. The experimental results show the linear effect in proportion to the number of slaves. In satisfiable instances
, the random division shows the good performance. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
SAT problem / parallel SAT solver / problem division / distribution and cooperation / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 108, no. 444, SS2008-52, pp. 23-28, March 2009. |
Paper # |
SS2008-52 |
Date of Issue |
2009-02-23 (SS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
SS2008-52 |
Conference Information |
Committee |
SS |
Conference Date |
2009-03-02 - 2009-03-03 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Saga University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
general |
Paper Information |
Registration To |
SS |
Conference Code |
2009-03-SS |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
A division technique for a SAT problem in a distributed SAT solver |
Sub Title (in English) |
|
Keyword(1) |
SAT problem |
Keyword(2) |
parallel SAT solver |
Keyword(3) |
problem division |
Keyword(4) |
distribution and cooperation |
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Akihide Takami |
1st Author's Affiliation |
Yamanashi University (Yamanashi Univ) |
2nd Author's Name |
Hidetomo Nabeshima |
2nd Author's Affiliation |
Yamanashi University (Yamanashi Univ) |
3rd Author's Name |
Koji Iwanuma |
3rd Author's Affiliation |
Yamanashi University (Yamanashi Univ) |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2009-03-02 16:15:00 |
Presentation Time |
30 minutes |
Registration for |
SS |
Paper # |
SS2008-52 |
Volume (vol) |
vol.108 |
Number (no) |
no.444 |
Page |
pp.23-28 |
#Pages |
6 |
Date of Issue |
2009-02-23 (SS) |
|