OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [testsuite/] [go.test/] [test/] [bench/] [shootout/] [fannkuch-parallel.go] - Blame information for rev 700

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 700 jeremybenn 
/*
2 
Redistribution and use in source and binary forms, with or without
3 
modification, are permitted provided that the following conditions are met:
4 
 
5 
    * Redistributions of source code must retain the above copyright
6 
    notice, this list of conditions and the following disclaimer.
7 
 
8 
    * Redistributions in binary form must reproduce the above copyright
9 
    notice, this list of conditions and the following disclaimer in the
10 
    documentation and/or other materials provided with the distribution.
11 
 
12 
    * Neither the name of "The Computer Language Benchmarks Game" nor the
13 
    name of "The Computer Language Shootout Benchmarks" nor the names of
14 
    its contributors may be used to endorse or promote products derived
15 
    from this software without specific prior written permission.
16 
 
17 
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18 
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 
ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21 
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22 
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23 
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25 
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27 
POSSIBILITY OF SUCH DAMAGE.
28 
*/
29 
 
30 
/*
31 
 * The Computer Language Benchmarks Game
32 
 * http://shootout.alioth.debian.org/
33 
 *
34 
 * contributed by The Go Authors.
35 
 * Based on fannkuch.scala by Rex Kerr
36 
 */
37 
 
38 
package main
39 
 
40 
import (
41 
        "flag"
42 
        "fmt"
43 
        "runtime"
44 
)
45 
 
46 
var n = flag.Int("n", 7, "count")
47 
var nCPU = flag.Int("ncpu", 4, "number of cpus")
48 
 
49 
type Job struct {
50 
        start []int
51 
        n     int
52 
}
53 
 
54 
type Found struct {
55 
        who *Kucher
56 
        k   int
57 
}
58 
 
59 
type Kucher struct {
60 
        perm []int
61 
        temp []int
62 
        flip []int
63 
        in   chan Job
64 
}
65 
 
66 
func NewKucher(length int) *Kucher {
67 
        return &Kucher{
68 
                perm: make([]int, length),
69 
                temp: make([]int, length),
70 
                flip: make([]int, length),
71 
                in:   make(chan Job),
72 
        }
73 
}
74 
 
75 
func (k *Kucher) permute(n int) bool {
76 
        i := 0
77 
        for ; i < n-1 && k.flip[i] == 0; i++ {
78 
                t := k.perm[0]
79 
                j := 0
80 
                for ; j <= i; j++ {
81 
                        k.perm[j] = k.perm[j+1]
82 
                }
83 
                k.perm[j] = t
84 
        }
85 
        k.flip[i]--
86 
        for i > 0 {
87 
                i--
88 
                k.flip[i] = i
89 
        }
90 
        return k.flip[n-1] >= 0
91 
}
92 
 
93 
func (k *Kucher) count() int {
94 
        K := 0
95 
        copy(k.temp, k.perm)
96 
        for k.temp[0] != 0 {
97 
                m := k.temp[0]
98 
                for i := 0; i < m; i++ {
99 
                        k.temp[i], k.temp[m] = k.temp[m], k.temp[i]
100 
                        m--
101 
                }
102 
                K++
103 
        }
104 
        return K
105 
}
106 
 
107 
func (k *Kucher) Run(foreman chan<- Found) {
108 
        for job := range k.in {
109 
                verbose := 30
110 
                copy(k.perm, job.start)
111 
                for i, v := range k.perm {
112 
                        if v != i {
113 
                                verbose = 0
114 
                        }
115 
                        k.flip[i] = i
116 
                }
117 
                K := 0
118 
                for {
119 
                        if verbose > 0 {
120 
                                for _, p := range k.perm {
121 
                                        fmt.Print(p + 1)
122 
                                }
123 
                                fmt.Println()
124 
                                verbose--
125 
                        }
126 
                        count := k.count()
127 
                        if count > K {
128 
                                K = count
129 
                        }
130 
                        if !k.permute(job.n) {
131 
                                break
132 
                        }
133 
                }
134 
                foreman <- Found{k, K}
135 
        }
136 
}
137 
 
138 
type Fanner struct {
139 
        jobind   int
140 
        jobsdone int
141 
        k        int
142 
        jobs     []Job
143 
        workers  []*Kucher
144 
        in       chan Found
145 
        result   chan int
146 
}
147 
 
148 
func NewFanner(jobs []Job, workers []*Kucher) *Fanner {
149 
        return &Fanner{
150 
                jobs: jobs, workers: workers,
151 
                in:     make(chan Found),
152 
                result: make(chan int),
153 
        }
154 
}
155 
 
156 
func (f *Fanner) Run(N int) {
157 
        for msg := range f.in {
158 
                if msg.k > f.k {
159 
                        f.k = msg.k
160 
                }
161 
                if msg.k >= 0 {
162 
                        f.jobsdone++
163 
                }
164 
                if f.jobind < len(f.jobs) {
165 
                        msg.who.in <- f.jobs[f.jobind]
166 
                        f.jobind++
167 
                } else if f.jobsdone == len(f.jobs) {
168 
                        f.result <- f.k
169 
                        return
170 
                }
171 
        }
172 
}
173 
 
174 
func swapped(a []int, i, j int) []int {
175 
        b := make([]int, len(a))
176 
        copy(b, a)
177 
        b[i], b[j] = a[j], a[i]
178 
        return b
179 
}
180 
 
181 
func main() {
182 
        flag.Parse()
183 
        runtime.GOMAXPROCS(*nCPU)
184 
        N := *n
185 
        base := make([]int, N)
186 
        for i := range base {
187 
                base[i] = i
188 
        }
189 
 
190 
        njobs := 1
191 
        if N > 8 {
192 
                njobs += (N*(N-1))/2 - 28 // njobs = 1 + sum(8..N-1) = 1 + sum(1..N-1) - sum(1..7)
193 
        }
194 
        jobs := make([]Job, njobs)
195 
        jobsind := 0
196 
 
197 
        firstN := N
198 
        if firstN > 8 {
199 
                firstN = 8
200 
        }
201 
        jobs[jobsind] = Job{base, firstN}
202 
        jobsind++
203 
        for i := N - 1; i >= 8; i-- {
204 
                for j := 0; j < i; j++ {
205 
                        jobs[jobsind] = Job{swapped(base, i, j), i}
206 
                        jobsind++
207 
                }
208 
        }
209 
 
210 
        nworkers := *nCPU
211 
        if njobs < nworkers {
212 
                nworkers = njobs
213 
        }
214 
        workers := make([]*Kucher, nworkers)
215 
        foreman := NewFanner(jobs, workers)
216 
        go foreman.Run(N)
217 
        for i := range workers {
218 
                k := NewKucher(N)
219 
                workers[i] = k
220 
                go k.Run(foreman.in)
221 
                foreman.in <- Found{k, -1}
222 
        }
223 
        fmt.Printf("Pfannkuchen(%d) = %d\n", N, <-foreman.result)
224 
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.