Rendering with AErender Launcher
There are several rendering modes implemented in AErender Launcher.
- Single Composition, Single Thread: Standard rendering process, nothing special about that. Could be useful sometimes, especially on Apple computers.
- Single Composition, Multiple Threads: Duration of composition in frames divides automatically to a number of threads. As a result, total render time could be shortened up to the 4x times (maybe higher, but it's fastest acceleration that I achived), because all render processes will be launched simultaneously. And of course, it really depends on your CPU horsepower and available RAM, so try not to overload your computer with all the render threads. Though, you can limit RAM available for each aerender right inside Launcher.
- Multiple Compositions, Single Thread for each: You can render up to 100 compositions from one project simultaneously. But you need to type every composition name to make this happen. And again, it's still very dependable on your CPU and RAM.
Upcoming rendering modes
- Network multi-machine rendering
- Automated rendering


Welcome
Physics Electronic Circuits Calculator
Physics Calculator
Power, Voltage, Current, and Resistance
Power (P) :
W
Voltage (V) :
V
Current (I) :
Micro
Base
A
Resistance (R) :
OHM
Only enter information into two boxes! It may get "confused" or solve incorrectly otherwise.
Power consumption over time
Power Rating :
W
Seconds :
Minutes :
Hours :
Days :
Months* :
*Calculated as 30 days, recommended to use days instead
Years :
Convert to :
Kilowatt-Hours
Joules
Price Per KwH (Optional) :
$
Energy Usage :
KwH
Cost :


Ranjit Endurthi - EDA Blog
A Happy life is one spent in learning, earning and yearning
Home
Cultural
Technical
Projects
Contact
Projects
Coming Soon...
Connect with me


4 references to AddAddressesToMailMessage
Microsoft.PowerShell.Commands.Utility (4)
commands\utility\Send-MailMessage.cs (4)
247
AddAddressesToMailMessage
(To, "to");
252
AddAddressesToMailMessage
(Bcc, "bcc");
258
AddAddressesToMailMessage
(Cc, "cc");
264
AddAddressesToMailMessage
(ReplyTo, "replyTo");


uk.ac.manchester.cs.mekon
for general description).See: Description
| Interface | Description |
|---|---|
| ICustomFrameMatcher |
Interface whose implementations will provide customised query
matching for specified frame-valued slot-types, to override
the basic subsumption-based matching provided by the
IMatcher implementations. |
| ICustomNumberMatcher |
Interface whose implementations will provide customised query
matching for specified number-valued slot-types, to override
the default subsumption-based matching provided by the
IMatcher implementations. |
| ICustomStringMatcher |
Interface whose implementations will provide customised query
matching for specific string-valued slot-types, to override
the default subsumption-based matching provided by the
IMatcher implementations (which for string-valued
slot-types means simple equality checking). |
| ICustomValueMatcher |
Base-interface for value-type specific interfaces whose
implementations will provide customised query matching for
the relevant value-types for specified slot-types, to
override the default subsumption-based matching provided
by the
IMatcher implementations. |
| IDiskStoreNames |
Defines file and directory names used by the disk-based
instance-store implementation.
|
| IMatcher |
Provides mechanisms for storing and executing queries over
representations of sets of instantiations of a MEKON Frames
Model (FM).
|
| IMatcherIndexes |
Provides mapping for each unique instance identity to a
corresponding unique index value.
|
| IProfileSerialiserVocab |
Vocabulary for the XML serialisation of instance profile
information as represented by the disk-based instance-store
within instance-profile files.
|
| Class | Description |
|---|---|
| IDiskStoreBuilder |
Provides mechanisms for building a disk-based instance-store, as
represented by an
IStore object. |
| IInstanceProfile |
Represents profile information about an instance stored in
the disk-based instance-store.
|
| IMatcherConfig |
Provides configuation information that may be required by
implementations of
IMatcher |
| IMatchInstanceRefExpander | |
| IProfileSerialiser |
Provides XML serialisation of instance profile information
for the disk-based instance-store.
|
| IValueMatchCustomiser |
Provides customised query matching for a particular value-type,
via a specific
ICustomValueMatcher , together with a
particular set of applicable slot-types. |
uk.ac.manchester.cs.mekon
for general description).


{% extends "base2.html" %} {% block title %}Starfinder Inventory Generator{% endblock %} {% block description %}Random inventory generator to help fill your Starfinder stores{% endblock %} {% block css %} {% endblock %} {% block body %}
Generates store inventories for your Starfinder games. Perfect for printing and handing out to players.


Meaningful solutions to America's gun violence epidemic are getting lost in a cycle of despair and outrage that define the media's response to gun tragedies. And nothing ever changes as a result.
At the Guardian, we do not accept the orthodoxy that the debate about gun control is simply too difficult. Our new series, Break the Cycle, will challenge the way the media covers gun violence. It will drive an ongoing conversation about possible solutions, and hold politicians to account for ignoring reforms that could save lives. Your support will fund our in-depth reporting on guns throughout 2018.
To drive change in America, we need to recognize that gun rights advocates are important partners — and that citizens on all sides want to make the country safer. We will address gun violence in all its forms: not just mass shootings, but the more than 100 people killed daily in suicides, domestic violence, and accidental killings, and the disproportionate burden of gun violence on communities of color.
By keeping the issue of gun violence in the public eye outside of major tragedies, we can keep the US and the world informed and create meaningful change.
If you have questions or comments about Break the Cycle, you can reach us via email. We're also seeking larger contributions to support the Guardian's reporting on gun violence from foundations, companies and individuals. If you would like to get involved with this project or provide matching funds, please contact us via email.
The Guardian will allocate all funds up to $200,000 raised by this project to its core operations that will fund our extended coverage of gun violence in America, including editing, reporting, visuals and new commissions. The Guardian will allocate additional funds beyond the first $200,000 towards its core operations that fund our in-depth reporting on topics including national affairs, politics, criminal justice, and gun violence. Contributions will not be returned. You can read additional terms and conditions here.
The ultimate owner of the Guardian is the Scott Trust Limited, whose role it is to secure the editorial and financial independence of the Guardian in perpetuity. Reader contributions support the Guardian’s journalism.
Please note that the Guardian is not a charity, will not use your support for charitable programs, and your support of the Guardian’s journalism does not constitute a charitable donation. As such your contribution is not eligible to be treated as a charitable deduction for federal or state taxes in the United States or elsewhere.
Please note that the Guardian is not a charity, will not use your support for charitable
programs, and your support of the Guardian’s journalism does not constitute a
charitable donation. As such your contribution is not eligible to be treated as a
charitable deduction for federal or state taxes in the United States or elsewhere.
If you have any questions about contributing to the Guardian, please contact us here.


Simple HR
Home
Departments
Company Directory
Positions
Recruitment
Employee Management
Leave Management
Payroll


home
about us
reviews
Login
Enter Valid details
Email address
Password
Forget the password ?
Sign in
keep me logged-in
New User
Toggle navigation
Colour List
Blush colours
Eye shade colours
Shimmers
Base Makeup
Foundations
Concealers
Compacts
Eyes
Mascaras
Liners
Eyebrow Shades
Lip Shades & Gloss
Nail Shades & Gloss
Others
Previous
Next


The DocBook DSSSL Stylesheets package contains DSSSL stylesheets. These are used by OpenJade or other tools to transform SGML and XML DocBook files.
This package is known to build and work properly using an LFS-9.1 platform.
Download (HTTP): https://downloads.sourceforge.net/docbook/docbook-dsssl-1.79.tar.bz2
Download (FTP): ftp://ftp.mirrorservice.org/sites/distfiles.gentoo.org/distfiles/docbook-dsssl-1.79.tar.bz2
Download MD5 sum: bc192d23266b9a664ca0aba4a7794c7c
Download size: 277 KB
Estimated disk space required: 14 MB
Estimated build time: less than 0.1 SBU
Documentation and test data
Download (HTTP): https://downloads.sourceforge.net/docbook/docbook-dsssl-doc-1.79.tar.bz2
Download MD5 sum: 9a7b809a21ab7d2749bb328334c380f2
Download size: 142 KB
docbook-3.1, docbook-4.5, OpenSP-1.5.2 and OpenJade-1.3.2
User Notes: http://wiki.linuxfromscratch.org/blfs/wiki/docbook-dsssl
If you downloaded the documentation, run:
tar -xf ../docbook-dsssl-doc-1.79.tar.bz2 --strip-components=1
Install DocBook DSSSL Stylesheets
by running the following commands as the root
user:
install -v -m755 bin/collateindex.pl /usr/bin && install -v -m644 bin/collateindex.pl.1 /usr/share/man/man1 && install -v -d -m755 /usr/share/sgml/docbook/dsssl-stylesheets-1.79 && cp -v -R * /usr/share/sgml/docbook/dsssl-stylesheets-1.79 && install-catalog --add /etc/sgml/dsssl-docbook-stylesheets.cat \ /usr/share/sgml/docbook/dsssl-stylesheets-1.79/catalog && install-catalog --add /etc/sgml/dsssl-docbook-stylesheets.cat \ /usr/share/sgml/docbook/dsssl-stylesheets-1.79/common/catalog && install-catalog --add /etc/sgml/sgml-docbook.cat \ /etc/sgml/dsssl-docbook-stylesheets.cat
The above commands create an installation script for this package.
The following commands will perform the necessary tests to confirm
that your installed DocBook SGML toolchain will produce desired
results. You must have the docbook-3.1, docbook-4.5, OpenSP-1.5.2 and
OpenJade-1.3.2 packages installed and perform
the tests as the root
user.
All tests will be performed from the /usr/share/sgml/docbook/dsssl-stylesheets-1.79/doc/testdata
directory as the root
user:
cd /usr/share/sgml/docbook/dsssl-stylesheets-1.79/doc/testdata
The first test should produce no output to stdout (your screen) and
create a file named jtest.rtf
in the
current directory:
openjade -t rtf -d jtest.dsl jtest.sgm
The next test should return only the following line to stdout:
onsgmls:I: "OpenSP" version
"1.5.2"
onsgmls -sv test.sgm
The next test should produce no output to stdout and create a file
named test.rtf
in the current
directory:
openjade -t rtf \ -d /usr/share/sgml/docbook/dsssl-stylesheets-1.79/print/docbook.dsl \ test.sgm
The last test should produce no output to stdout and create a file
named c1.htm
in the current
directory:
openjade -t sgml \ -d /usr/share/sgml/docbook/dsssl-stylesheets-1.79/html/docbook.dsl \ test.sgm
Finally, clean up:
rm jtest.rtf test.rtf c1.htm
Last updated on 2020-02-16 15:15:05 -0800


--- title: Winter War with the Russian Terrorist State excerpt: Russian defeat must be total and unconditional. date: '2022-11-30 06:50:01 +0100' categories: - General - Motivation image: path: /assets/images/social/winter_war.jpg ---
On this day in 1939 (Nov 30), Russia attacked Finland, the country I was born in. That was the start of the Winter War, and later the Continuation War. That was 83 years ago.
Today, in 2022, the Russian terrorist state is doing the same in Ukraine, committing another genocide of Ukrainians.
Once again we're against a hallucinating Kremlin dictator and a failed empire, and once again the Russians fascists are suffering heavy casualties. Only this time, their defeat must be total and unconditional.
Slava Ukraini! 🇺🇦


Khameleon Library
Home
Books
Books by category
Authors
Contacts
Random Book
Add Author
Add Book
Sign Out


Home
Menu
Keg List
Contact us
$5
Founders Azacca IPA
ABV 7% Grand Rapids, MI
On Tap Calendar
On Tap
Off Tap
Duration
1/22/2016 6:02:45 PM
2/2/2016 5:07:17 PM
10.96 Days
2/12/2019 9:16:32 PM
Still on
9.81 Days (so far)


By far, the closest analogy to this work is the great work of BrowserID during the Mozilla Personas effort (postmortem here). In many ways, the goals that BrowserID was trying to achieve as well as the mechanisms that were created are a lot alike what’s being proposed here. There are significant differences in strategy and design, but let’s start with the similarities first because there are many.
First, BrowserID was clearly trying to solve similar problems, namely IDP Tracking and friction. The mechanisms that were created clearly had strong builtin privacy components to prevent IDPs from knowing about RPs and vice versa, via the chain of signatures gathered from IDPs (mainly email providers) and certificates generated by the browser.
Second, from a mechanism perspective, there was clearly a separation between an RP to Browser API as well as a Browser to IDP API.
navigator.id.get((assertion) => {}, {
backgroundColor: "#606B72",
siteName: "My Example Site"
});
The RP calls a browser native API to fetch an assertion which gets mediated by the browser in coordination with the IDP.
// set up UI
navigator.id.beginAuthentication(function(email) {
// update UI to display the email address
});
The postmortem analysis here is very insightful in understanding what were the challenges faced and gives this proposal a solid place to work from. In many ways, we think some of these insights are rooted in the observation we made earlier about backwards compatibility with RPs and user’s current behavior, which we are deliberately trying to avoid.
Related Work
- Building a More Private Web
- Personas and navigator.id
- WebOTP
- Credential Manager
- Add your work here


Function-chapter officers should act as chapter leaders, serve as role models for chapter members, and assist the advisor in the management of chapter affairs and activities.
Selection-the chapter officers may be nominated and elected by chapter members, selected by the advisor, or selected by any other means decided by the chapter. Any method for chapter officer selection should be clearly outlined in the local chapter bylaws.
Briarcliff Officer Selection Process: For the 2016-2017 school year, the Tri-M advisor of Briarcliff chapter #3229 did not select the chapter officers. A general election was not held by the membership in the spring of 2016. The following will be considered to elect or select officers:
Tri-M membership in good standing
Written essay and application stating one's interest in performing the duties of the office for the Briarcliff chapter
Past participation record in Tri-M
Balanced representation from the different performing ensembles
Due to the absence of seniors during the 4th quarter, certain officer positions can only be filled by juniors and sophomores.
Tri-M members who are in good standing and wish to apply for one of the aforementioned offices must:
Submit a one-page essay in 12-font, single-spaced, 1-inch margins, in New Times Roman script explaining how you will fulfill your duties as a Tri-M officer.
Prepare and present a two-minute speech to the membership during the chapter meeting, outlining your intentions to fulfill the duties of said office.
THE FIRST TRI-M MEETING FOR CURRENT MEMBERS IS WEDNESDAY, SEPTEMBER 7, 2016. ELECTIONS/SELECTIONS OF OFFICERS WILL BE CONSIDERED ON THAT DATE.
This position is only open to 11th and 12th graders. The chapter president will lead the members toward the attainment of the goals of the chapter and of the Tri-M Music Honor Society. The president will:
Preside at all meetings of the chapter and of the executive committee.
Lead the induction ceremony for new members.
Lead the Tri-M song before each meeting
Create the agenda for chapter meetings (to be submitted to and reviewed by the chapter advisor two days prior to the scheduled meetings)
Coordinate Kids Care events (see Kids Care)
The position is only open to 10th and 11th graders. The chapter vice president will:
Publicize meetings and other activities
Lead the induction ceremony for new members
Educates new members on the history of Tri-M
Assist the president in all Tri-M endeavors
Maintain the Tri-M hall bulletin board
The chapter treasurer is open to all grade levels. The treasurer will:
Collect all membership dues
Keep an accurate record of all monies received and disbursed
Present a report of the chapter's finances at each meeting
Sign all applicable forms
The chapter historian is open to all grade levels. The historian will:
Teach the Tri-M Loyalty Song
Keeps record of chapter activities
Keep a comprehensive record of all programs presented by the chapter and its members (including pictures and news clippings; serve as publicity chairperson)
Compile and be responsible for the chapter’s entry for Chapter of the Year, as feasible.
Kids Care is a program that provides a musical community service. In the past, Briarcliff students, along with dedicated parent volunteers, coordinated "acts" at agreed upon sites. The acts largely consisted of music performances that lasted from 30 - 45 minutes, taking place on Sunday afternoons between 2 and 3PM. Student members, performing as soloists or ensemble members, prepared these performances on their own time. As part of the chapter president's responsibilities, the president will assume the following Kid's Care responsibilities:
Organize and oversee performances for sites
Coordinate travel arrangements to sites with parent volunteers and performing Tri-M members
Oversee rehearsal and performance "readiness"s prior to site visits
Make monthly reports and invitations to membership about KC needs
Serve as liaison between parents, chapter membership and site/facility managers
Make arrangements to provide flowers that will be distributed to the residents at each site at the end of the performance
Introduce all "acts" and provide opening and closing remarks for site visits


Home
Survival Facts
My Escapes
Greatest Warriors
Armory
LOGOUT
Close ×
HOME
SURVIVAL FACTS
GREATEST WARRIORS
ARMORY
MY ESCAPES
LOGOUT
00:00:00
Jump the timer ahead by 54 minutes
End Day
It is coming to get you...
Escape by locking your screen for at least 15 mins
×
At least 6 minutes have passed...
UNLOCK SCREEN
Unlock
OOPS!!.
You survived the day with no substantial damage. Collect your gift and check it out in your Armory!
Got It
Jump the timer ahead by 54 minutes


You are viewing an historical archive of past issues. Please report new issues to the appropriate project issue tracker on GitHub.
Comments
-
anonymous
try running
$ PATH=$PATH:/System/Library/Frameworks/Ruby.framework/Versions/1.8/Headers/
and then ruby extconf.rb
-
Greg Hurrell
Closing due to lack of activity.
-
Greg Hurrell
Status changed:
- From: new
- To: closed
Add a comment
Comments are now closed for this issue.


| DOSE: |
18 mg |
oral |
2C-B |
(liquid) |
I submit this report mostly in the interest of having a longitudinal log, rather than as a particularly novel or noteworthy event in itself. This is perhaps somewhere around the 40th or 50th time I've ingested 2C-B over the course of 6.5 years.
We attended a wedding party after the main ceremony. During and after the ceremony, I'd had several glasses of wine and was feeling mentally softened. The ceremony had been fun and emotional and I was in a giggly, open mood.
I had suspected something other than alcohol might be available and a couple hours after the ceremony ended, someone was appointed as the inviter, who went around the room and told people where they could go to get 2C-B if they wanted and consult briefly if the person wasn't exactly sure about it.
The 2C-B was being dispensed from a large bottle, having been dissolved at around 1ml per milligram or so. They asked how much I wanted, I told them 18mg, and they used a graduated cylinder to measure the volume and poured it into my glass.
The taste was typical 2C-B flavor, bitter chemical with that tinge of something else. It would be impossible for me to reliably tell the difference between different phenethylamines, despite having tasted a variety of them over a number of years.
I chose 18mg because thats my favorite social level. Not usually too strong, but with enough impact that I am shifted off my normally curmudgeonly, impatient self.
The wine was still in my head as I felt the 2C-B begin to permeate my CNS. Where I had been slowly losing cognitive steam over the last hour, now I felt a tingling surge of increased sociability. It was between 30 and 60 minutes when the effects began to be unmistakeable. I hadn't eaten a dinner and so my stomach wasn't full. I'd had some snacks here and there all day and a largish breakfast.
The physical stimulation was about the same as a strong dose of caffeine for me, which can be quite stimulating. With my 25-75mg per day caffeine habit, this would probably have been like a good 100-150mg dose of caffeine.. in the area of a strong coffee or a double cappucino for me.
A smile got planted on my face as I talked to friends from around the country whom I hadn't seen in some time. With one friend, I talked about my interest in the question of how people decide what they think is true, what constitutes knowledge and self-identification of 'truth', to which he replied that he is interested in how people make decisions, how to talk about decision making which is non-rational.. like why people take non-physically addicting recreational psychoactives in ways which are counter to their own logical decision making. It was an interesting conversation which was interrupted by the natural chaotic flow of a building full of friends.
I realized that my partner had disappeared and I hadn't seen her since she came up, so I decided to try to find her. In my somewhat non-linear mental state, I walked the entirety of the building twice and failed to find her. I began what I call my 'exhaustive search' protocol which I use when I can't find what I'm looking for. This is simply to go to the place where I expect something to be, then exhaustively search every possible location, even ones which are unlikely. I become very methodical as the only way to be sure that I'm actually looking at the things in front of my eyes. Soon after I started this, I found my love tucked behind the large foliage in the entry hall, entwined with a friend who had taken some MDMA and was looking for some comfort as she came up in a group of people she didn't know very well.
Often at parties where we are taking 2C-B and others are taking MDMA, it is an interaction that we have that the MDMA-people are far more touchy and needy than we get on the 2C-B. It is an interesting vantage point to experience the MDMA-mindspace from, with a sense of amusement and empathy, but with a substantial sense of distance from the smooshiness of that very boundary-softening chemical.
I was invited into and climbed into the pile in the corner. After a few minutes of this, it was clear the mood had dissipated and we all went back to the main fray. Some people were dancing, some frenetically, to the music. Per usual, I felt more like socializing than dancing and ended up seeking someone else to talk to.
Another friend and I spent some time talking about the complexities of human relationships, about how difficult it is to communicate. It strikes me, over and over, how humans are a species which is genetically predisposed to communication. We are, among the fauna of this planet, perhaps one of the most communication-oriented creatures. Wired to speak, wired to think abstractly, forepaws free to manipulate tools and keyboards to concretize language...
Yet, despite our predisposition for it, it is surprisingly hard, imprecise, prone to dramatic miscommunication. With those we love and have the best intentions for, we can still spend so much time in utter confusion. We often choose to communicate in ways which are obscure or oblique, often against our own best interests or wishes. Its a very confusing species to be.
Her relationship was at one of those points where she was questioning whether she and her boyfriend were just coming from contexts where they were just too different, their understandings of the world incompatible, so that their communications never really sorted themselves out.
It was a good conversation that we were struggling with trying to work out some insight and shared understanding... but again, as is the norm in these environments, the conversation collided with the chaos of phenethylamined social groupings. As we sat talking, a group of people sat down in front of us and began engaging us in banter.
The evening continued in the mode of having brief but fairly clear conversations with friends for several hours. People started to trickle out of the party-space, saying their goodbyes, while the folks who had chosen to take a stim stayed later.
Around T+5 or so, my partner said she was feeling jittery and a little physically uncomfortable. In retrospect, she should have taken a benzo (alprazolam) earlier on and didn't end up taking one until just before sleep. The phenethylamine-jitters, which I get fairly routinely on many of these shulginalikes, often consist of a feeling of buzzing or energy or tension in muscles. One of the things that is somewhat disconcerting about it is that it can often manifest in the largest muscles in the body, like the gluteus, thighs, calves, shoulders, etc, as a twitching or shaking. It is not so bothersome in short spurts, but my partner was experiencing it for a couple hours. Again, in retrospect, some type of calmer would have gone a long way to improve her enjoyment of the evening.
Overall, the experience was very enjoyable for me and helped create a sense of connection to the other wedding participants. I've been to dozens of weddings and often alcohol alone can be OK to help create a sense of shared experience, but having mild mind-stimulators and empathogens around can certainly give some more space to interact. So many people come from around the country to spend time together, its nice to have 6-8 hours of time together where there is no external obligation and people are in a good mood.
18mg was once again the right dose for me. Very light visuals, noticeable stimulation, mood lift, mild empathogenesis, social, fairly clear headed, not too gushy.
Needed to take .5mg alprazolam to get to sleep, which carried a bit of a hangover into the next day.
Experience Reports are the writings and opinions of the individual authors who submit them.
Some of the activities described are dangerous and/or illegal and none are recommended by Erowid.


Information: If your funds been moved out of your wallet on 5th June 2019, please fill this form with all info required. This form is only for HUSH. If you want to claim other coins, please use the specific form for those coins from the list below. If you have multiple addres...


This initiative is the brainchild of Ayu Lodha who started it when she was 15-year-old student who believes in the phrase "Each Life Matters” and wants to make sure that this message reaches people enmasse
Find Out MoreThe motto of Shashakt is to educate youngsters and adults alike about the many laws and provisions that our judiciary system has for animals and how to go about implementing them in the legal manner. It also aims to let the society understand that it is our duty to be compassionate towards animals, make people aware about every species, educate them with the basic techniques to be used in the rescue of animals.
Shashakt aims to make all these happen by having awareness campaigns every week with a new theme for each week. The founding principle on which Shashakt is being initiated is "Why All Animals Matter". The purview of Shashakt does not stop the focus on dogs and cats but all other species of animals.
This initiative believes in changing the perception of people, which is "Somebody Must Do Something" to "I Must Do Something".
Shashakt focuses on three main factors
Animal Welfare
Animal Rights
Species Education
We humans tend to have the thought, "Why don't somebody do something?". Particularly in the cases of animal cruelty, people tend to wash their hands off and expect others to "do something", without "doing anything" themselves.
Finally, Shashakt aims to shake off this practice of saying “Somebody Must do something” and bring in change by implementing the thought of “I,We Must Do Something” in the minds of people. Together we all can bring about a change.
We campaign for animal rights & welfare.
We educate people about various scenarios they can encounter with animals.
We rescue animals from critical situations.
If animals aren't ready to be released back to streets.. We foster them until they are ready again.
If you see an animal in danger please give us a call. For other queries such a public speaking send us an email and we will get back to you as soon as possible!
+91 95382 73866


© 2013, NVIDIA CORPORATION. All rights reserved.
Code and text by Sean Baxter, NVIDIA Research.
(Click here for license. Click here for contact information.)
Run many concurrent searches where both the needles and haystack arrays are sorted. This input condition lets us recast the function as a sequential process resembling merge, rather than as a traditional binary search. Complexity improves from A log B to A + B, and because we touch every input, a search can retrieve not just the lower-bound of A into B but simultaneously the upper-bound of B into A, plus flags for all elements indicating if matches in the other array exist.
Vectorized sorted search (lower_bound A into B) benchmark from benchmarksortedsearch/benchmarksortedsearch.cu
Vectorized sorted search demostration from tests/demo.cu
void DemoSortedSearch(CudaContext& context) { printf("\n\nSORTED SEARCH DEMONSTRATION:\n\n"); // Use CudaContext::SortRandom to generate a haystack of 200 random integers // between 0 and 999 and an array of 100 needles in the same range. int HaystackSize = 200; int NeedlesSize = 100; MGPU_MEM(int) haystack = context.SortRandom<int>(HaystackSize, 0, 299); MGPU_MEM(int) needles = context.SortRandom<int>(NeedlesSize, 0, 299); printf("Haystack array:\n"); PrintArray(*haystack, "%4d", 10); printf("\nNeedles array:\n"); PrintArray(*needles, "%4d", 10); // Run a vectorized sorted search to find lower bounds. SortedSearch<MgpuBoundsLower>(needles->get(), NeedlesSize, haystack->get(), HaystackSize, needles->get(), context); printf("\nLower bound array:\n"); PrintArray(*needles, "%4d", 10); }
SORTED SEARCH DEMONSTRATION: Haystack array: 0: 0 5 5 7 7 7 7 8 9 9 10: 10 11 12 14 15 15 16 17 19 19 20: 20 24 25 28 28 29 31 33 36 36 30: 37 38 40 42 42 43 45 46 49 50 40: 51 51 51 52 53 55 56 57 60 60 50: 61 61 62 62 64 66 68 69 73 74 60: 79 81 82 84 85 88 90 90 95 97 70: 99 101 105 108 108 111 115 118 118 119 80: 119 119 119 122 122 123 125 126 126 130 90: 133 133 135 135 139 140 143 145 145 146 100: 147 149 149 149 154 158 160 161 165 166 110: 168 169 170 172 172 174 174 174 175 175 120: 175 177 179 182 183 184 186 187 188 190 130: 192 193 194 196 198 199 199 205 205 208 140: 209 215 217 218 218 218 220 220 221 221 150: 223 224 225 230 234 234 235 240 240 243 160: 244 249 250 251 252 253 253 254 255 255 170: 255 257 258 258 259 262 263 265 267 270 180: 270 274 278 278 278 279 280 281 284 284 190: 284 285 285 292 294 295 296 296 296 298 Needles array: 0: 3 3 12 16 16 17 17 19 20 21 10: 24 27 27 28 30 31 35 39 40 42 20: 52 52 53 53 54 55 57 58 62 63 30: 72 75 83 86 86 89 92 95 98 98 40: 99 99 99 100 104 105 107 109 110 111 50: 112 117 118 121 124 126 129 132 133 139 60: 140 148 156 160 161 167 168 173 179 186 70: 191 198 202 202 212 212 214 220 223 229 80: 233 239 245 254 256 256 260 268 269 269 90: 271 271 272 273 277 285 296 296 299 299 Lower bound array: 0: 1 1 12 16 16 17 17 18 20 21 10: 21 23 23 23 26 26 28 32 32 33 20: 43 43 44 44 45 45 47 48 52 54 30: 58 60 63 65 65 66 68 68 70 70 40: 70 70 70 71 72 72 73 75 75 75 50: 76 77 77 83 86 87 89 90 90 94 60: 95 101 105 106 107 110 110 115 122 126 70: 130 134 137 137 141 141 141 146 150 153 80: 154 157 161 167 171 171 175 179 179 179 90: 181 181 181 181 182 191 196 196 200 200
Vectorized sorted search (complete search) benchmark from benchmarksortedsearch/benchmarksortedsearch.cu
Vectorized sorted search demostration (2) from tests/demo.cu
void DemoSortedSearch2(CudaContext& context) { printf("\n\nSORTED SEARCH DEMONSTRATION (2):\n\n"); int ACount = 100; int BCount = 100; MGPU_MEM(int) aData = context.SortRandom<int>(ACount, 0, 299); MGPU_MEM(int) bData = context.SortRandom<int>(BCount, 0, 299); MGPU_MEM(int) aIndices = context.Malloc<int>(ACount); MGPU_MEM(int) bIndices = context.Malloc<int>(BCount); printf("A array:\n"); PrintArray(*aData, "%4d", 10); printf("\nB array:\n"); PrintArray(*bData, "%4d", 10); // Run a vectorized sorted search to find lower bounds. SortedSearch<MgpuBoundsLower, MgpuSearchTypeIndexMatch, MgpuSearchTypeIndexMatch>(aData->get(), ACount, bData->get(), BCount, aIndices->get(), bIndices->get(), context); printf("\nLower bound of A into B (* for match):\n"); PrintArrayOp(*aIndices, FormatOpMaskBit("%c%3d"), 10); printf("\nUpper bound of B into A (* for match):\n"); PrintArrayOp(*bIndices, FormatOpMaskBit("%c%3d"), 10); }
SORTED SEARCH DEMONSTRATION (2): A array: 0: 0 3 5 13 14 15 16 18 18 21 10: 24 26 26 30 31 32 38 38 38 40 20: 60 72 72 74 81 83 86 88 88 89 30: 89 99 99 101 101 102 114 115 118 118 40: 119 128 136 139 145 148 149 150 151 151 50: 157 160 164 165 167 177 181 181 182 182 60: 189 190 191 192 196 197 199 200 207 212 70: 213 213 216 218 220 222 223 228 231 233 80: 233 234 234 234 239 239 240 247 249 264 90: 265 267 271 271 275 277 282 284 293 298 B array: 0: 1 2 15 23 24 25 25 25 25 27 10: 27 29 30 31 33 33 35 39 45 49 20: 58 59 61 61 62 63 64 67 67 68 30: 70 71 82 85 87 87 88 91 98 98 40: 109 110 110 116 116 118 121 121 126 129 50: 129 134 145 155 159 165 174 174 179 181 60: 183 186 192 192 196 196 201 202 204 205 70: 205 208 209 212 216 218 220 222 224 227 80: 231 233 233 234 235 236 250 251 251 253 90: 260 263 272 275 276 285 289 291 291 293 Lower bound of A into B (* for match): 0: 0 2 2 2 2 * 2 3 3 3 3 10: * 4 9 9 * 12 * 13 14 17 17 17 18 20: 22 32 32 32 32 33 34 * 36 * 36 37 30: 37 40 40 40 40 40 43 43 * 45 * 45 40: 46 49 52 52 * 52 53 53 53 53 53 50: 54 55 55 * 55 56 58 * 59 * 59 60 60 60: 62 62 62 * 62 * 64 66 66 66 71 * 73 70: 74 74 * 74 * 75 * 76 * 77 78 80 * 80 * 81 80: * 81 * 83 * 83 * 83 86 86 86 86 86 92 90: 92 92 92 92 * 93 95 95 95 * 99 100 Upper bound of B into A (* for match): 0: 1 1 * 6 10 * 11 11 11 11 11 13 10: 13 13 * 14 * 15 16 16 16 19 20 20 20: 20 20 21 21 21 21 21 21 21 21 30: 21 21 25 26 27 27 * 29 31 31 31 40: 36 36 36 38 38 * 40 41 41 41 42 50: 42 42 * 45 50 51 * 54 55 55 56 * 58 60: 60 60 * 64 * 64 * 65 * 65 68 68 68 68 70: 68 69 69 * 70 * 73 * 74 * 75 * 76 77 77 80: * 79 * 81 * 81 * 84 84 84 89 89 89 89 90: 89 89 94 * 95 95 98 98 98 98 * 99
//////////////////////////////////////////////////////////////////////////////// // kernels/sortedsearch.cuh // Vectorized sorted search. This is the most general form of the function. // Executes two simultaneous linear searches on two sorted inputs. // Bounds: // MgpuBoundsLower - // lower-bound search of A into B. // upper-bound search of B into A. // MgpuBoundsUpper - // upper-bound search of A into B. // lower-bound search of B into A. // Type[A|B]: // MgpuSearchTypeNone - no output for this input. // MgpuSearchTypeIndex - return search indices as integers. // MgpuSearchTypeMatch - return 0 (no match) or 1 (match). // For TypeA, returns 1 if there is at least 1 matching element in B // for element in A. // For TypeB, returns 1 if there is at least 1 matching element in A // for element in B. // MgpuSearchTypeIndexMatch - return search indices as integers. Most // significant bit is match bit. // aMatchCount, bMatchCount - If Type is Match or IndexMatch, return the total // number of elements in A or B with matches in B or A, if the pointer is // not null. This generates a synchronous cudaMemcpyDeviceToHost call that // callers using streams should be aware of. template<MgpuBounds Bounds, MgpuSearchType TypeA, MgpuSearchType TypeB, typename InputIt1, typename InputIt2, typename OutputIt1, typename OutputIt2, typename Comp> MGPU_HOST void SortedSearch(InputIt1 a_global, int aCount, InputIt2 b_global, int bCount, OutputIt1 aIndices_global, OutputIt2 bIndices_global, Comp comp, CudaContext& context, int* aMatchCount = 0, int* bMatchCount = 0); // SortedSearch specialized with Comp = mgpu::less<T>. template<MgpuBounds Bounds, MgpuSearchType TypeA, MgpuSearchType TypeB, typename InputIt1, typename InputIt2, typename OutputIt1, typename OutputIt2> MGPU_HOST void SortedSearch(InputIt1 a_global, int aCount, InputIt2 b_global, int bCount, OutputIt1 aIndices_global, OutputIt2 bIndices_global, CudaContext& context, int* aMatchCount = 0, int* bMatchCount = 0); // SortedSearch specialized with // TypeA = MgpuSearchTypeIndex // TypeB = MgpuSearchTypeNone // aMatchCount = bMatchCount = 0. template<MgpuBounds Bounds, typename InputIt1, typename InputIt2, typename OutputIt, typename Comp> MGPU_HOST void SortedSearch(InputIt1 a_global, int aCount, InputIt2 b_global, int bCount, OutputIt aIndices_global, Comp comp, CudaContext& context); // SortedSearch specialized with Comp = mgpu::less<T>. template<MgpuBounds Bounds, typename InputIt1, typename InputIt2, typename OutputIt> MGPU_HOST void SortedSearch(InputIt1 a_global, int aCount, InputIt2 b_global, int bCount, OutputIt aIndices_global, CudaContext& context); // SortedEqualityCount returns the difference between upper-bound (computed by // this function) and lower-bound (passed as an argument). That is, it computes // the number of occurences of a key in B that match each key in A. // The provided operator must have a method: // int operator()(int lb, int ub) const; // It returns the count given the lower- and upper-bound indices. // // An object SortedEqualityOp is provided: // struct SortedEqualityOp { // MGPU_HOST_DEVICE int operator()(int lb, int ub) const { // return ub - lb; // } // }; template<typename InputIt1, typename InputIt2, typename InputIt3, typename OutputIt, typename Comp, typename Op> MGPU_HOST void SortedEqualityCount(InputIt1 a_global, int aCount, InputIt2 b_global, int bCount, InputIt3 lb_global, OutputIt counts_global, Comp comp, Op op, CudaContext& context); // Specialization of SortedEqualityCount with Comp = mgpu::less<T>. template<typename InputIt1, typename InputIt2, typename InputIt3, typename OutputIt, typename Op> MGPU_HOST void SortedEqualityCount(InputIt1 a_global, int aCount, InputIt2 b_global, int bCount, InputIt3 lb_global, OutputIt counts_global, Op op, CudaContext& context);
Searching data is a critical part of all computing systems. On the GPU, because of the extreme width of the processor, we need to be a bit creative to fully utilize the device while executing a search. The Thrust library includes vectorized binary searches in which all threads in the grid run their own independent binary search on sorted inputs. The user passes multiple "needles" (the keys you search for) and a sorted "haystack" (what you are looking in). Thousands of needles are required to fill the width of the machine.
Even when batching a large array of queries, performance will drag if the needles are unsorted—random access to the haystack results in many cache misses. GPU cache lines are 128 bytes, and if querying 4-byte data types, sustained throughput will only hit 3% of peak bandwidth.
This project focuses on functions that take one or more sorted inputs and emit a sorted output. Consider taking this requirement to vectorized binary searching: rather than accept the divergent memory accesses caused by queries on random needles, we could sort needles to keep the L2 cache hot. Instead of using 3% of each fetched cache line, we'd expect high re-use of cache lines between neighboring threads. The same embarrassingly-parallel vectorized search function achieves much higher throughput with better data organization. Searching for sorted needles in a haystack is a well-motivated problem. Consider joining two database tables—these are likely both sorted coming off disk, will need to be in sorted order to perform a sort-merge join, and want sorted results to return as a rowset.
The work presented in previous MGPU pages inspired a specific algorithmic optimization to this problem of vectorized searching. If the needles are sorted, the lower- or upper-bound results must also be sorted. That is, if a binary search for key1 returns index1, a search for key2 >= key1 must return index2 >= index1. In the sequential implementation, if we're searching for key2 having already computed the result for key1, we can improve performance slightly by searching the interval (index1, end) rather than (begin, end), since index2 cannot appear in (begin, index1).
There is a still stronger optimization: turn the binary search (O(A log B) complexity, where A is the needle array and B is the haystack) into a linear search (O(A + B) complexity). Starting with pointers A and B at the heads of the needle and haystack arrays, respectively:
If B (haystack) is less than A (needle), advance B. Because the elements in A are sorted, we aren't advancing B past any possible results for yet-to-be-encountered elements in A.
Otherwise, the B pointer is the result for the A query. Set results[A] = B and advance to the next query in A.
Sorted search for CPU from benchmarksortedsearch/benchmarksortedsearch.cu
// Return lower-bound of A into B. template<MgpuBounds Bounds, typename T, typename Comp> void CPUSortedSearch(const T* a, int aCount, const T* b, int bCount, int* indices, Comp comp) { int aIndex = 0, bIndex = 0; while(aIndex < aCount) { bool p; if(bIndex >= bCount) p = true; else p = (MgpuBoundsUpper == Bounds)? comp(a[aIndex], b[bIndex]) : !comp(b[bIndex], a[aIndex]); if(p) indices[aIndex++] = bIndex; else ++bIndex; } }
This code is obviously more efficient than processing each needle as a binary search. But what we've gained in work-efficiency we may have lost in parallelism: binary searches are embarassingly parallel while this linear search code processes queries sequentially.
It's instructive to compare CPUSortedSearch
with SerialMerge
, the GPU function that powers MGPU's merge and mergesort:
template<int VT, bool RangeCheck, typename T, typename Comp> MGPU_DEVICE void SerialMerge(const T* keys_shared, int aBegin, int aEnd, int bBegin, int bEnd, T* results, int* indices, Comp comp) { T aKey = keys_shared[aBegin]; T bKey = keys_shared[bBegin]; #pragma unroll for(int i = 0; i < VT; ++i) { bool p; if(RangeCheck) p = (bBegin >= bEnd) || ((aBegin < aEnd) && !comp(bKey, aKey)); else p = !comp(bKey, aKey); results[i] = p ? aKey : bKey; indices[i] = p ? aBegin : bBegin; if(p) aKey = keys_shared[++aBegin]; else bKey = keys_shared[++bBegin]; } __syncthreads(); }
Although they have some differences, both routines check out-of-range pointers and set the predicate appropriately. If both pointers are in-range, keys are compared with the comparator object. For sorted search, if A (the needle) is smaller, the output is set and A is incremented; if B (the haystack) is smaller, B is incremented. For serial merge, if A is smaller, output is stored and A is incremented; if B is smaller, output is stored and B is incremented. The only material difference between these routines is how results are returned: the traversals over the input arrays are identical.
We parallelize the vectorized sorted search just like we do the merge. Coarse- and fine-grained scheduling and partitioning code is reused from MGPU Merge. However because we stream over A and B data but only emit A elements, we need an additional in-CTA pass to compact results.
There is a surprising and welcomed benefit from using a linear search, beyond just the improved work-efficiency: If we search for the lower-bound of A into B, we can also recover the upper-bound of B into A in the same pass. This is possible with linear search because we encounter every element from B; it does not hold with binary search.
Sorted search (2) for CPU from benchmarksortedsearch/benchmarksortedsearch.cu
// Return lower-bound of A into B and upper-bound of B into A. template<typename T, typename Comp> void CPUSortedSearch2(const T* a, int aCount, const T* b, int bCount, int* aIndices, int* bIndices, Comp comp) { int aIndex = 0, bIndex = 0; while(aIndex < aCount || bIndex < bCount) { bool p; if(bIndex >= bCount) p = true; else if(aIndex >= aCount) p = false; else p = !comp(b[bIndex], a[aIndex]); if(p) aIndices[aIndex++] = bIndex; else bIndices[bIndex++] = aIndex; } }
The inputs are traversed in the same order as in CPUSortedSearch
(and in merge), but there is now an output on every iteration. This function looks very much like merge. We even lose the sense of 'needles' and 'haystack,' as the arrays are treated symmetrically. Scheduling and partioning the parallel version will be handled the same as merge. This is further evidence for the argument presented in the introduction and reiterated through these pages: we gain flexibility, clarity, and performance by separating partitioning/scheduling and work logic.
Sorted search (3) for CPU from benchmarksortedsearch/benchmarksortedsearch.cu
// Return lower-bound of A into B and set the high bit if A has a match in B. // Return upper-bound of B into A and set the high bit if B has a match in A. template<typename T, typename Comp> void CPUSortedSearch3(const T* a, int aCount, const T* b, int bCount, int* aIndices, int* bIndices, Comp comp) { int aIndex = 0, bIndex = 0; while(aIndex < aCount || bIndex < bCount) { bool p; if(bIndex >= bCount) p = true; else if(aIndex >= aCount) p = false; else p = !comp(b[bIndex], a[aIndex]); if(p) { // Compare the current key in A with the current key in B. bool match = bIndex < bCount && !comp(a[aIndex], b[bIndex]); aIndices[aIndex++] = bIndex + ((int)match<< 31); } else { // Compare the current key in B with the previous key in A. bool match = aIndex && !comp(a[aIndex - 1], b[bIndex]); bIndices[bIndex++] = aIndex + ((int)match<< 31); } } }
The second version of the sorted search is augmented with additional compares. It sets the most significant bit of the output index if the corresponding key in A or B has a match in the complementary array. We're supporting comparators (C++-style), so to test equality we must verify that both !(A < B) and !(B < A). Fortunately the state of the two pointers implies one half of the expression for both match tests.
Advancing A (lower-bound search): We know that B cannot be less than A (or else we would be advancing B!). We can test for equality simply by testing that A is not less than B: !comp(a[aIndex], b[bIndex])
.
Advancing B (upper-bound search): The match in A (if there is one) must be the previous element in A, a[aIndex - 1]
. However because we got to this point, we know that B is not less than the previous element in A: if it were, then when examining the previous A we would have advanced B rather than A, and we wouldn't be at this state. The expression !comp(a[aIndex - 1], b[bIndex])
is all that is needed to test equality.
Vectorized sorted search is a detailed and information-heavy function. That it runs nearly as fast as merge encourages its use in many situations. It has a pleasing symmetry with merge, and in fact we can re-implement merge using vectorized sorted search to produce indices and Bulk Insert to insert data at these indices.
Load-balancing search, an amazingly useful intra-CTA utility, is a straight-forward specialization of vectorized sorted search. We demonstate pairing vectorized sorted search with load-balancing search to implement relational joins in a later page.
include/kernels/sortedsearch.cuh
template<int NT, int VT, MgpuBounds Bounds, bool IndexA, bool MatchA, bool IndexB, bool MatchB, typename InputIt1, typename InputIt2, typename T, typename Comp> MGPU_DEVICE int2 DeviceLoadSortedSearch(int4 range, InputIt1 a_global, int aCount, InputIt2 b_global, int bCount, int tid, int block, T* keys_shared, int* indices_shared, Comp comp) { int a0 = range.x; int a1 = range.y; int b0 = range.z; int b1 = range.w; int aCount2 = a1 - a0; int bCount2 = b1 - b0; // For matching: // If UpperBound // MatchA requires preceding B // MatchB requires trailing A // If LowerBound // MatchA requires trailing B // MatchB requires preceding A int leftA = MatchB && (MgpuBoundsLower == Bounds) && (a0 > 0); int leftB = MatchA && (MgpuBoundsUpper == Bounds) && (b0 > 0); int rightA = a1 < aCount; int rightB = b1 < bCount; int aStart = leftA; int aEnd = aStart + aCount2 + rightA; int bStart = aEnd + leftB; int bEnd = bStart + bCount2 + rightB; // Cooperatively load all the data including halos. DeviceLoad2ToShared<NT, VT, VT + 1>(a_global + a0 - leftA, aEnd, b_global + b0 - leftB, bEnd - aEnd, tid, keys_shared); // Run the serial searches and compact the indices into shared memory. bool extended = rightA && rightB && (!MatchA || leftB) && (!MatchB || leftA); int2 matchCount = CTASortedSearch<NT, VT, Bounds, IndexA, MatchA, IndexB, MatchB>(keys_shared, aStart, aCount2, aEnd, a0, bStart, bCount2, bEnd, b0, extended, tid, indices_shared, comp); return matchCount; }
One vectorized sorted search kernel supports many modes of operation. The host function that launches KernelSortedSearch
separates the MgpuSearchType
enums into individual flags for IndexA
, MatchA
, IndexB
, and MatchB
. The kernel calls DeviceLoadSortedSearch
which loads the intervals from the A and B arrays, runs a MergePath
search on each thread, and performs a serial search over VT inputs per thread.
Different modes have different requirements:
| Lower-bound | Upper-bound | |
| MatchA | trailing B | preceding B |
| MatchB | preceding A | trailing A |
Merge Path partitioning divides A and B inputs into distinct, non-overlapping intervals. Loading just these intervals into a tile's shared memory is insufficient to support match operations. For a lower-bound search, equal elements are consumed from A before B. If an element A[i] has a match in B at B[j], B[j] will appear after A[i] in the Merge Path. The thread checking the match of A[i] needs access to B[j], even if B[j] is mapped to a subsequent tile.
The search types are decomposed and the interval pointers incremented or decremented to accommodate the extra terms requried to verify matches. DeviceLoad2ToShared
cooperatively loads intervals from two source arrays and stores to shared memory. It incorporates an optimization to handle extended cases like this: for a nominal tile (i.e. all tiles except the partial tile at the end) each thread loads VT items—these VT loads are included in an unpredicated form, written to encourage maximum outstanding loads and reduce latency. At most the kernel loads only four additional items beyond this (one each for the preceding and trailing items from A and B), and only this final load is predicated. In other words: DeviceLoad2ToShared<NT, VT, VT + 1>
generates an optimized path for full tiles, in which the first VT loads are unpredicated and the last load is predicated.
If a "halo" element has been loaded after the last A and B inputs, the extended
flag is set and we omit range checks in the serial search code. CTASortedSearch
computes search indices and matches into shared memory and returns match counts (of both A into B and B into A) to the caller. The calling function, KernelSortedSearch
, copies the indices and match flags out of shared memory and into their respective output arrays.
include/device/ctasortedsearch.cuh
template<int NT, int VT, MgpuBounds Bounds, bool IndexA, bool MatchA, bool IndexB, bool MatchB, typename T, typename Comp> MGPU_DEVICE int2 CTASortedSearch(T* keys_shared, int aStart, int aCount, int aEnd, int a0, int bStart, int bCount, int bEnd, int b0, bool extended, int tid, int* indices_shared, Comp comp) { // Run a merge path to find the start of the serial search for each thread. int diag = VT * tid; int mp = MergePath<Bounds>(keys_shared + aStart, aCount, keys_shared + bStart, bCount, diag, comp); int a0tid = mp; int b0tid = diag - mp; // Serial search into register. int3 results; int indices[VT]; if(extended) results = DeviceSerialSearch<VT, Bounds, false, IndexA, MatchA, IndexB, MatchB>(keys_shared, a0tid + aStart, aEnd, b0tid + bStart, bEnd, a0 - aStart, b0 - bStart, indices, comp); else results = DeviceSerialSearch<VT, Bounds, true, IndexA, MatchA, IndexB, MatchB>(keys_shared, a0tid + aStart, aEnd, b0tid + bStart, bEnd, a0 - aStart, b0 - bStart, indices, comp); __syncthreads(); // Compact the indices into shared memory. Use the decision bits (set is A, // cleared is B) to select the destination. int decisions = results.x; b0tid += aCount; #pragma unroll for(int i = 0; i < VT; ++i) { if((1<< i) & decisions) { if(IndexA || MatchA) indices_shared[a0tid++] = indices[i]; } else { if(IndexB || MatchB) indices_shared[b0tid++] = indices[i]; } } __syncthreads(); // Return the match counts for A and B keys. return make_int2(results.y, results.z); }
CTASortedSearch
follows the same recipe that makes MGPU Merge (and Mergesort and Segmented Sort) so efficient, but adds a few twists:
The host function calls MergePathPartitions
to globally partition the input arrays into tile-sized chunks, as in merge.
In the sorted search kernel, data is cooperatively loaded from A and B arrays into shared memory.
Each thread runs a MergePath
search for every VT * tid cross-diagonal.
DeviceSerialSearch
is invoked with the offsets from 3. Each thread traverses VT elements in an unrolled loop and computes search results. Search indices/matches are returned in the order in which they are encountered. The set of decision bits are returned in order in results.x
.
After synchronization, each thread steps through its VT indices and distributes them to either the A or B output arrays.
The number of A matches in B and B matches in A are returned to the caller, which may then use CTAReduce
to find a total within the tile, and atomically increment the global match counters.
include/device/ctasortedsearch.cuh
template<int VT, MgpuBounds Bounds, bool RangeCheck, bool IndexA, bool MatchA, bool IndexB, bool MatchB, typename T, typename Comp> MGPU_DEVICE int3 DeviceSerialSearch(const T* keys_shared, int aBegin, int aEnd, int bBegin, int bEnd, int aOffset, int bOffset, int* indices, Comp comp) { const int FlagA = IndexA ? 0x80000000 : 1; const int FlagB = IndexB ? 0x80000000 : 1; T aKey = keys_shared[aBegin]; T bKey = keys_shared[bBegin]; T aPrev, bPrev; if(aBegin > 0) aPrev = keys_shared[aBegin - 1]; if(bBegin > 0) bPrev = keys_shared[bBegin - 1]; int decisions = 0; int matchCountA = 0; int matchCountB = 0; #pragma unroll for(int i = 0; i < VT; ++i) { bool p; if(RangeCheck && aBegin >= aEnd) p = false; else if(RangeCheck && bBegin >= bEnd) p = true; else p = (MgpuBoundsUpper == Bounds) ? comp(aKey, bKey) : !comp(bKey, aKey); if(p) { // aKey is smaller than bKey, so it is inserted before bKey. // Save bKey's index (bBegin + first) as the result of the search // and advance to the next needle in A. bool match = false; if(MatchA) { // Test if there is an element in B that matches aKey. if(MgpuBoundsUpper == Bounds) { bool inRange = !RangeCheck || (bBegin > aEnd); match = inRange && !comp(bPrev, aKey); } else { bool inRange = !RangeCheck || (bBegin < bEnd); match = inRange && !comp(aKey, bKey); } } int index = 0; if(IndexA) index = bOffset + bBegin; if(match) index |= FlagA; if(IndexA || MatchA) indices[i] = index; matchCountA += match; // Mark the decision bit to indicate that this iteration has // progressed A (the needles). decisions |= 1<< i; aPrev = aKey; aKey = keys_shared[++aBegin]; } else { // aKey is larger than bKey, so it is inserted after bKey (but we // don't know where yet). Advance the B index to the next element in // the haystack to continue the search for the current needle. bool match = false; if(MatchB) { if(MgpuBoundsUpper == Bounds) { bool inRange = !RangeCheck || ((bBegin < bEnd) && (aBegin < aEnd)); match = inRange && !comp(bKey, aKey); } else { bool inRange = !RangeCheck || ((bBegin < bEnd) && (aBegin > 0)); match = inRange && !comp(aPrev, bKey); } } int index = 0; if(IndexB) index = aOffset + aBegin; if(match) index |= FlagB; if(IndexB || MatchB) indices[i] = index; matchCountB += match; // Keep the decision bit cleared to indicate that this iteration // has progressed B (the haystack). bPrev = bKey; bKey = keys_shared[++bBegin]; } } return make_int3(decisions, matchCountA, matchCountB); }
DeviceSerialSearch
is a massive function that services the many permutations that vectorized sorted search supports. Search results are stored directly into the indices
register array and are redistributed into shared memory by CTASortedSearch
. Rather than having to provision space for both the source and destination in shared memory, halving occupancy, we provision only enough for the source data—outputs are produced into register; the CTA is synchronized; and the results are stored back to the same shared memory array.
When run on full tiles, DeviceSerialSearch
is specialized with RangeCheck = false
(corresponding to extended = true
in CTASortedSearch
), allowing it to elide range-checking logic that adds significant latency to execution. This is an optimization that can be made for merge, mergesort, and segmented mergesort as well. However, it has been prioritized here because A) there's potentially much more logic here to contend with; and B) DeviceLoadSortedSearch
already is loading in halo elements to support match operations, so adding a specialization to elide range checks took minimal effort.
While reviewing the logic for the four match tests, keep in mind that equality is established with two less-than checks: !(aKey < bKey) && !(bKey < aKey);
or when written with comparators: !comp(aKey, bKey) && !comp(bKey, aKey)
.
When computing the lower-bound of A into B (and the upper-bound of B into A);
To match A (p = true): We're inserting aKey
before bKey
. If there is a match for aKey
it must be bKey
. Check that bKey
is in range and equal to aKey
. Half of the equality test has already been computed when we made the predicate test !comp(bKey, aKey)
. Check the other half of the equality condition with a second comparison: !comp(aKey, bKey).
To match B (p = false): The predicate test has confirmed that bKey
is smaller than aKey
(comp(bKey, aKey)
is true). If there is a match for bKey
it must be aPrev
. The previous A-advancing iteration proved that !comp(bKey, aPrev)
. Check the other half of the equality condition with a second comparison: !comp(aPrev, bKey).
When computing the upper-bound of A into B (and the lower-bound of B into A) we flip the arguments around:
To match A (p = true): We're inserting aKey after bKey. If there is a match for aKey
it must be bPrev
. Check that bPrev
is in range and equal to aKey
. The previous A-advancing iteration proved that !comp(aKey, bPrev)
; it failed the comp(aKey, bKey)
test and advanced B to get us to this point. Check the other half of the equality condition with a second comparison: !comp(bPrev, aKey).
To match B (p = false): The predicate test has confirmed that aKey
is not smaller than bKey
. If there is a match for bKey
it must be aKey
. Check the other half of the equality condition with a second comparison: !comp(bKey, aKey).
Vectorized sorted search is a powerful merge-like function. It's put to good use when implementing relational joins. More importantly, it motivates the useful and elegant load-balancing search, the subject of the next page.
include/kernels/sortedsearch.cuh
struct SortedEqualityOp { MGPU_HOST_DEVICE int operator()(int lb, int ub) const { return ub - lb; } }; template<typename Tuning, typename InputIt1, typename InputIt2, typename InputIt3, typename OutputIt, typename Comp, typename Op> MGPU_LAUNCH_BOUNDS void KernelSortedEqualityCount(InputIt1 a_global, int aCount, InputIt2 b_global, int bCount, const int* mp_global, InputIt3 lb_global, OutputIt counts_global, Comp comp, Op op) { typedef MGPU_LAUNCH_PARAMS Params; const int NT = Params::NT; const int VT = Params::VT; const int NV = NT * VT; union Shared { int keys[NT * (VT + 1)]; int indices[NV]; }; __shared__ Shared shared; int tid = threadIdx.x; int block = blockIdx.x; int4 range = ComputeMergeRange(aCount, bCount, block, 0, NV, mp_global); // Compute the upper bound. int2 matchCount = DeviceLoadSortedSearch<NT, VT, MgpuBoundsUpper, true, false, false, false>(range, a_global, aCount, b_global, bCount, tid, block, shared.keys, shared.indices, comp); int aCount2 = range.y - range.x; // Load the lower bounds computed by the previous launch. int lb[VT]; DeviceGlobalToReg<NT, VT>(aCount2, lb_global + range.x, tid, lb); // Subtract the lower bound from the upper bound and store the count. counts_global += range.x; #pragma unroll for(int i = 0; i < VT; ++i) { int index = NT * i + tid; if(index < aCount2) { int count = op(lb[i], shared.indices[index]); counts_global[index] = count; } } }
C++ standard library functions std::equal_range binary searches for a single key in an array and returns the pair of (lower-bound, upper-bound) iterators. std::count runs a similar search but returns the count of occurrences, which is equal to the difference of the upper- and lower-bounds.
Vectorized sorted search doesn't extend naturally to support equal-range queries in a single pass because partitioning and scheduling decisions are made specifically for either lower- or upper-bound duplicate semantics. We can, at least, provide a modest optimization for achieving a vectorized count function. Rather than running lower- and upper-bound searches independently and launching a third kernel to take differences, we've provided a SortedSearch
specialization that finds upper-bound indices of A into B, then loads lower-bound indices that correspond to each output and computes and stores counts directly.
SortedEqualityCount
is specialized over a user-provided difference operator. This adds flexibility to the function, allowing it to extract index bits of a match-decorated sorted search result, or to max the difference with a constant. (It's this usage that enables our relational left-join function.)


subject = "You have a notification!" layout = "system" == Hello {{ toUser.name|title }}, {{ fromUser.name|title }} wants you to join his group. Click http://octoberfriends.dma.org/group/request here to accept his request. ==
Hello {{ toUser.name|title }},
{{ fromUser.name|title }} wants you to join his group. Click here to accept his request.


| Top |
Functions
| NcmLapackWS * | ncm_lapack_ws_new () |
| NcmLapackWS * | ncm_lapack_ws_dup () |
| void | ncm_lapack_ws_free () |
| void | ncm_lapack_ws_clear () |
| gint | ncm_lapack_dptsv () |
| gint | ncm_lapack_dpotrf () |
| gint | ncm_lapack_dpotri () |
| gint | ncm_lapack_dpotrs () |
| gint | ncm_lapack_dposv () |
| gint | ncm_lapack_dsytrf () |
| gint | ncm_lapack_dsytrs () |
| gint | ncm_lapack_dsytri () |
| gint | ncm_lapack_dsysv () |
| gint | ncm_lapack_dsysvx () |
| gint | ncm_lapack_dsysvxx () |
| gint | ncm_lapack_dsyevr () |
| gint | ncm_lapack_dsyevd () |
| gint | ncm_lapack_dgeev () |
| gint | ncm_lapack_dgeevx () |
| gint | ncm_lapack_dgeqrf () |
| gint | ncm_lapack_dgerqf () |
| gint | ncm_lapack_dgeqlf () |
| gint | ncm_lapack_dgelqf () |
| GArray * | ncm_lapack_dggglm_alloc () |
| gint | ncm_lapack_dggglm_run () |
| gint | ncm_lapack_dgels () |
| gint | ncm_lapack_dgelsd () |
| #define | NCM_LAPACK_CHECK_INFO() |
Description
This object is dedicated to encapsulate functions from LAPACK choosing the most suitable backend.
Priority order: (1) LAPACK and (2) GSL. It no longer tries to use clapack or lapacke, it is faster and simpler to stick to fortran's lapack.
The description of each function follows its respective LAPACK documentation.
Functions
ncm_lapack_ws_dup ()
NcmLapackWS *
ncm_lapack_ws_dup (NcmLapackWS *ws
);
Duplicates a Lapack workspace object.
ncm_lapack_ws_clear ()
void
ncm_lapack_ws_clear (NcmLapackWS **ws
);
Clears a Lapack workspace object.
ncm_lapack_dptsv ()
gint ncm_lapack_dptsv (gdouble *d
,gdouble *e
,gdouble *b
,gdouble *x
,gint n
);
This function computes the solution to a real system of linear equations
$A*X = B$ (B = b
), where $A$ is an N-by-N (N = n
) symmetric positive definite tridiagonal
matrix, and $X$ and $B$ are N-by-NRHS (NRHS = 1) matrices.
$A$ is factored as $A = L*D*L^T$, and the factored form of $A$ is then used to solve the system of equations.
ncm_lapack_dpotrf ()
gint ncm_lapack_dpotrf (gchar uplo
,gint n
,gdouble *a
,gint lda
);
This function computes the Cholesky factorization of a real symmetric
positive definite matrix a
.
The factorization has the form
$A = U^T * U$, if uplo
= 'U', or
$A = L * L^T$, if uplo
= 'L',
where A = a
, $U$ is an upper triangular matrix and $L$ is lower triangular.
ncm_lapack_dpotri ()
gint ncm_lapack_dpotri (gchar uplo
,gint n
,gdouble *a
,gint lda
);
This function computes the inverse of a real symmetric positive
definite matrix a
= A using the Cholesky factorization
$A = U^T*U$ or $A = L*L^T$ computed by ncm_lapack_dpotrf()
.
ncm_lapack_dpotrs ()
gint ncm_lapack_dpotrs (gchar uplo
,gint n
,gint nrhs
,gdouble *a
,gint lda
,gdouble *b
,gint ldb
);
This function computes the solution of $A X = B$ for a real symmetric positive
definite matrix a
= A using the Cholesky factorization $A = U^T*U$ or $A = L*L^T$
already performed by ncm_lapack_dpotrf()
.
On entry b
contain the vectors $B$ and on exit b
contain the solutions if the return
is 0.
Parameters
uplo |
'U' upper triangle of |
|
n |
The order of the matrix |
|
nrhs |
Number of right-hand-side vectors to solve |
|
a |
array of doubles with dimension ( |
|
lda |
The leading dimension of the array |
|
b |
array of doubles with dimension ( |
|
ldb |
The leading dimension of the array |
ncm_lapack_dposv ()
gint ncm_lapack_dposv (gchar uplo
,gint n
,gint nrhs
,gdouble *a
,gint lda
,gdouble *b
,gint ldb
);
This function computes the solution of $A X = B$ for a real symmetric positive
definite matrix a
= A using the Cholesky factorization $A = U^T*U$ or $A = L*L^T$.
On entry b
contain the vectors $B$ and on exit b
contain the solutions if the return
is 0.
Parameters
uplo |
'U' upper triangle of |
|
n |
The order of the matrix |
|
nrhs |
Number of right-hand-side vectors to solve |
|
a |
array of doubles with dimension ( |
|
lda |
The leading dimension of the array |
|
b |
array of doubles with dimension ( |
|
ldb |
The leading dimension of the array |
ncm_lapack_dsytrf ()
gint ncm_lapack_dsytrf (gchar uplo
,gint n
,gdouble *a
,gint lda
,gint *ipiv
,NcmLapackWS *ws
);
This function computes the factorization of a real symmetric
matrix a
, using the Bunch-Kaufman diagonal pivoting method.
ncm_lapack_dsytrs ()
gint ncm_lapack_dsytrs (gchar uplo
,gint n
,gint nrhs
,gdouble *a
,gint lda
,gint *ipiv
,gdouble *b
,gint ldb
);
This function computes the solution of $A X = B$ for a real symmetric positive
definite matrix a
= A using the Cholesky factorization $A = U^T*U$ or $A = L*L^T$
already performed by ncm_lapack_dpotrf()
.
On entry b
contain the vectors $B$ and on exit b
contain the solutions if the return
is 0.
Parameters
uplo |
'U' upper triangle of |
|
n |
The order of the matrix |
|
nrhs |
Number of right-hand-side vectors to solve |
|
a |
array of doubles with dimension ( |
|
lda |
The leading dimension of the array |
|
ipiv |
Information about decomposition swaps and blocks |
|
b |
array of doubles with dimension ( |
|
ldb |
The leading dimension of the array |
ncm_lapack_dsytri ()
gint ncm_lapack_dsytri (gchar uplo
,gint n
,gdouble *a
,gint lda
,gint *ipiv
,NcmLapackWS *ws
);
This function compute the inverse of a real symmetric indefinite matrix a
using
the factorization a
= U*D*U**T or a
= L*D*L**T computed by ncm_lapack_dsytrf()
.
ncm_lapack_dsysv ()
gint ncm_lapack_dsysv (gchar uplo
,gint n
,gint nrhs
,gdouble *a
,gint lda
,gint *ipiv
,gdouble *b
,gint ldb
,gdouble *work
,gint lwork
);
Purpose
DSYSV uses the diagonal pivoting factorization to compute the solution to a real system of linear equations A * X = B, where A is an N-by-N symmetric matrix and X and B are N-by-NRHS matrices.
Parameters
uplo |
UPLO is CHARACTER*1 |
|
n |
N is INTEGER |
|
nrhs |
NRHS is INTEGER |
|
a |
A is DOUBLE PRECISION array, dimension (LDA,N) |
|
lda |
LDA is INTEGER |
|
ipiv |
IPIV is INTEGER array, dimension (N) |
|
b |
B is DOUBLE PRECISION array, dimension (LDB,NRHS) |
|
ldb |
LDB is INTEGER |
|
work |
WORK is DOUBLE PRECISION array, dimension (MAX(1,LWORK)) |
|
lwork |
LWORK is INTEGER |
ncm_lapack_dsysvx ()
gint ncm_lapack_dsysvx (gchar fact
,gchar uplo
,gint n
,gint nrhs
,gdouble *a
,gint lda
,gdouble *af
,gint ldaf
,gint *ipiv
,gdouble *b
,gint ldb
,gdouble *x
,gint ldx
,gdouble *rcond
,gdouble *ferr
,gdouble *berr
,gdouble *work
,gint lwork
,gint *iwork
);
Purpose
DSYSVX uses the diagonal pivoting factorization to compute the solution to a real system of linear equations A * X = B, where A is an N-by-N symmetric matrix and X and B are N-by-NRHS matrices.
Error bounds on the solution and a condition estimate are also provided.
Description
The following steps are performed:
-
If FACT = 'N', the diagonal pivoting method is used to factor A. The form of the factorization is - A = U * D * U**T, if UPLO = 'U', or
A = L * D * L**T, if UPLO = 'L', where U (or L) is a product of permutation and unit upper (lower) triangular matrices, and D is symmetric and block diagonal with 1-by-1 and 2-by-2 diagonal blocks.
If some D(i,i)=0, so that D is exactly singular, then the routine returns with INFO = i. Otherwise, the factored form of A is used to estimate the condition number of the matrix A. If the reciprocal of the condition number is less than machine precision, INFO = N+1 is returned as a warning, but the routine still goes on to solve for X and compute error bounds as described below.
The system of equations is solved for X using the factored form of A.
Iterative refinement is applied to improve the computed solution matrix and calculate error bounds and backward error estimates for it.
Parameters
fact |
FACT is CHARACTER*1 |
|
uplo |
UPLO is CHARACTER*1 |
|
n |
N is INTEGER |
|
nrhs |
NRHS is INTEGER |
|
a |
A is DOUBLE PRECISION array, dimension (LDA,N) |
|
lda |
LDA is INTEGER |
|
af |
AF is DOUBLE PRECISION array, dimension (LDAF,N) |
|
ldaf |
LDA is INTEGER |
|
ipiv |
IPIV is INTEGER array, dimension (N) |
|
b |
B is DOUBLE PRECISION array, dimension (LDB,NRHS) |
|
ldb |
LDB is INTEGER |
|
x |
X is DOUBLE PRECISION array, dimension (LDX,NRHS) |
|
ldx |
LDX is INTEGER |
|
rcond |
RCOND is DOUBLE PRECISION |
|
ferr |
FERR is DOUBLE PRECISION array, dimension (NRHS) |
|
berr |
BERR is DOUBLE PRECISION array, dimension (NRHS) |
|
work |
WORK is DOUBLE PRECISION array, dimension (MAX(1,LWORK)) |
|
lwork |
LWORK is INTEGER |
|
iwork |
IWORK is INTEGER array, dimension (N) |
Returns
INFO is INTEGER
= 0: successful exit
< 0: if INFO = -i, the i-th argument had an illegal value
> 0: if INFO = i, and i is
<= N: D(i,i) is exactly zero. The factorization has been completed but the factor D is exactly singular, so the solution and error bounds could not be computed. RCOND = 0 is returned.
= N+1: D is nonsingular, but RCOND is less than machine precision, meaning that the matrix is singular to working precision. Nevertheless, the solution and error bounds are computed because there are a number of situations where the computed solution can be more accurate than the value of RCOND would suggest.
ncm_lapack_dsysvxx ()
gint ncm_lapack_dsysvxx (gchar fact
,gchar uplo
,gint n
,gint nrhs
,gdouble *a
,gint lda
,gdouble *af
,gint ldaf
,gint *ipiv
,gchar *equed
,gdouble *s
,gdouble *b
,gint ldb
,gdouble *x
,gint ldx
,gdouble *rcond
,gdouble *rpvgrw
,gdouble *berr
,const gint n_err_bnds
,gdouble *err_bnds_norm
,gdouble *err_bnds_comp
,const gint nparams
,gdouble *params
,gdouble *work
,gint *iwork
);
Purpose
DSYSVXX uses the diagonal pivoting factorization to compute the solution to a double precision system of linear equations A * X = B, where A is an N-by-N symmetric matrix and X and B are N-by-NRHS matrices.
If requested, both norm-wise and maximum component-wise error bounds are returned. DSYSVXX will return a solution with a tiny guaranteed error (O(eps) where eps is the working machine precision) unless the matrix is very ill-conditioned, in which case a warning is returned. Relevant condition numbers also are calculated and returned.
DSYSVXX accepts user-provided factorizations and equilibration factors; see the definitions of the FACT and EQUED options. Solving with refinement and using a factorization from a previous DSYSVXX call will also produce a solution with either O(eps) errors or warnings, but we cannot make that claim for general user-provided factorizations and equilibration factors if they differ from what DSYSVXX would itself produce.
Description
The following steps are performed:
-
If FACT = 'E', double precision scaling factors are computed to equilibrate the system:
diag(S)*A*diag(S) *inv(diag(S))*X = diag(S)*B Whether or not the system will be equilibrated depends on the scaling of the matrix A, but if equilibration is used, A is overwritten by diag(S)*A*diag(S) and B by diag(S)*B.
-
If FACT = 'N' or 'E', the LU decomposition is used to factor the matrix A (after equilibration if FACT = 'E') as
A = U * D * U**T, if UPLO = 'U', or
A = L * D * L**T, if UPLO = 'L', where U (or L) is a product of permutation and unit upper (lower) triangular matrices, and D is symmetric and block diagonal with 1-by-1 and 2-by-2 diagonal blocks.
If some D(i,i)=0, so that D is exactly singular, then the routine returns with INFO = i. Otherwise, the factored form of A is used to estimate the condition number of the matrix A (see argument RCOND). If the reciprocal of the condition number is less than machine precision, the routine still goes on to solve for X and compute error bounds as described below.
The system of equations is solved for X using the factored form of A.
By default (unless PARAMS(LA_LINRX_ITREF_I) is set to zero), the routine will use iterative refinement to try to get a small error and error bounds. Refinement calculates the residual to at least twice the working precision.
If equilibration was used, the matrix X is premultiplied by diag(R) so that it solves the original system before equilibration.
Some optional parameters are bundled in the PARAMS array. These settings determine how refinement is performed, but often the defaults are acceptable. If the defaults are acceptable, users can pass NPARAMS = 0 which prevents the source code from accessing the PARAMS argument.
Parameters
fact |
FACT is CHARACTER*1 |
|
uplo |
UPLO is CHARACTER*1 |
|
n |
N is INTEGER |
|
nrhs |
NRHS is INTEGER |
|
a |
A is DOUBLE PRECISION array, dimension (LDA,N) |
|
lda |
LDA is INTEGER |
|
af |
AF is DOUBLE PRECISION array, dimension (LDAF,N) |
|
ldaf |
LDA is INTEGER |
|
ipiv |
IPIV is INTEGER array, dimension (N) |
|
equed |
EQUED is CHARACTER*1 |
|
s |
S is DOUBLE PRECISION array, dimension (N) |
|
b |
B is DOUBLE PRECISION array, dimension (LDB,NRHS) |
|
ldb |
LDB is INTEGER |
|
x |
X is DOUBLE PRECISION array, dimension (LDX,NRHS) |
|
ldx |
LDX is INTEGER |
|
rcond |
RCOND is DOUBLE PRECISION |
|
rpvgrw |
RPVGRW is DOUBLE PRECISION |
|
berr |
BERR is DOUBLE PRECISION array, dimension (NRHS) |
|
n_err_bnds |
N_ERR_BNDS is INTEGER |
|
err_bnds_norm |
ERR_BNDS_NORM is DOUBLE PRECISION array, dimension (NRHS, N_ERR_BNDS) |
|
err_bnds_comp |
ERR_BNDS_COMP is DOUBLE PRECISION array, dimension (NRHS, N_ERR_BNDS) |
|
nparams |
NPARAMS is INTEGER |
|
params |
PARAMS is DOUBLE PRECISION array, dimension (NPARAMS) |
|
work |
WORK is DOUBLE PRECISION array, dimension (4*N) |
|
iwork |
IWORK is INTEGER array, dimension (N) |
Returns
INFO is INTEGER
= 0: Successful exit. The solution to every right-hand side is guaranteed.
< 0: If INFO = -i, the i-th argument had an illegal value
> 0 and <= N: U(INFO,INFO) is exactly zero. The factorization has been completed, but the factor U is exactly singular, so the solution and error bounds could not be computed. RCOND = 0 is returned.
= N+J: The solution corresponding to the Jth right-hand side is not guaranteed. The solutions corresponding to other right- hand sides K with K > J may not be guaranteed as well, but only the first such right-hand side is reported. If a small componentwise error is not requested (PARAMS(3) = 0.0) then the Jth right-hand side is the first with a normwise error bound that is not guaranteed (the smallest J such that ERR_BNDS_NORM(J,1) = 0.0). By default (PARAMS(3) = 1.0) the Jth right-hand side is the first with either a normwise or componentwise error bound that is not guaranteed (the smallest J such that either ERR_BNDS_NORM(J,1) = 0.0 or ERR_BNDS_COMP(J,1) = 0.0). See the definition of ERR_BNDS_NORM(:,1) and ERR_BNDS_COMP(:,1). To get information about all of the right-hand sides check ERR_BNDS_NORM or ERR_BNDS_COMP.
ncm_lapack_dsyevr ()
gint ncm_lapack_dsyevr (gchar jobz
,gchar range
,gchar uplo
,gint n
,gdouble *a
,gint lda
,gdouble vl
,gdouble vu
,gint il
,gint iu
,gdouble abstol
,gint *m
,gdouble *w
,gdouble *z
,gint ldz
,gint *isuppz
,NcmLapackWS *ws
);
FIXME
ncm_lapack_dsyevd ()
gint ncm_lapack_dsyevd (gchar jobz
,gchar uplo
,gint n
,gdouble *a
,gint lda
,gdouble *w
,NcmLapackWS *ws
);
FIXME
ncm_lapack_dgeev ()
gint ncm_lapack_dgeev (gchar jobvl
,gchar jobvr
,gint n
,gdouble *a
,gint lda
,gdouble *wr
,gdouble *wi
,gdouble *vl
,gint ldvl
,gdouble *vr
,gint ldvr
,gdouble *work
,gint lwork
);
This function computes the eigensystem for a real matrix a
= A.
Calling this function with lwork == -1 computed the ideal lwork
in work
[0].
Parameters
jobvl |
|
|
jobvr |
|
|
n |
The order of the matrix |
|
a |
array of doubles with dimension ( |
|
lda |
The leading dimension of the array |
|
wr |
contain the real part of the computed eigenvalues |
|
wi |
contain the imaginary part of the computed eigenvalues |
|
vl |
if |
|
ldvl |
the leading dimension of the array |
|
vr |
if |
|
ldvr |
the leading dimension of the array |
|
work |
work area, must have |
|
lwork |
work area size |
ncm_lapack_dgeevx ()
gint ncm_lapack_dgeevx (gchar balanc
,gchar jobvl
,gchar jobvr
,gchar sense
,gint n
,gdouble *a
,gint lda
,gdouble *wr
,gdouble *wi
,gdouble *vl
,gint ldvl
,gdouble *vr
,gint ldvr
,gint *ilo
,gint *ihi
,gdouble *scale
,gdouble *abnrm
,gdouble *rconde
,gdouble *rcondv
,gdouble *work
,gint lwork
,gint *iwork
);
This function computes the eigensystem for a real matrix a
= A.
Calling this function with lwork == -1 computed the ideal lwork
in work
[0].
Parameters
balanc |
FIXME |
|
jobvl |
|
|
jobvr |
|
|
sense |
FIXME |
|
n |
The order of the matrix |
|
a |
array of doubles with dimension ( |
|
lda |
The leading dimension of the array |
|
wr |
contain the real part of the computed eigenvalues |
|
wi |
contain the imaginary part of the computed eigenvalues |
|
vl |
if |
|
ldvl |
the leading dimension of the array |
|
vr |
if |
|
ldvr |
the leading dimension of the array |
|
ilo |
FIXME |
|
ihi |
FIXME |
|
scale |
FIXME |
|
abnrm |
FIXME |
|
rconde |
FIXME |
|
rcondv |
FIXME |
|
work |
work area, must have |
|
lwork |
work area size |
|
iwork |
FIXME |
ncm_lapack_dgeqrf ()
gint ncm_lapack_dgeqrf (gint m
,gint n
,gdouble *a
,gint lda
,gdouble *tau
,NcmLapackWS *ws
);
DGEQRF computes a QR factorization of a real M-by-N matrix A: A = Q * R.
Parameters
m |
M is INTEGER The number of rows of the matrix A. M >= 0. |
|
n |
N is INTEGER The number of columns of the matrix A. N >= 0. |
|
a |
A is DOUBLE PRECISION array, dimension (LDA,N) On entry, the M-by-N matrix A. On exit, the elements on and above the diagonal of the array contain the min(M,N)-by-N upper trapezoidal matrix R (R is upper triangular if m >= n); the elements below the diagonal, with the array TAU, represent the orthogonal matrix Q as a product of min(m,n) elementary reflectors (see Further Details). |
|
lda |
LDA is INTEGER The leading dimension of the array A. LDA >= max(1,M). |
|
tau |
TAU is DOUBLE PRECISION array, dimension (min(M,N)) The scalar factors of the elementary reflectors (see Further Details). |
|
ws |
ncm_lapack_dgerqf ()
gint ncm_lapack_dgerqf (gint m
,gint n
,gdouble *a
,gint lda
,gdouble *tau
,NcmLapackWS *ws
);
DGERQF computes a RQ factorization of a real M-by-N matrix A: A = R * Q.
Parameters
m |
M is INTEGER The number of rows of the matrix A. M >= 0. |
|
n |
N is INTEGER The number of columns of the matrix A. N >= 0. |
|
a |
A is DOUBLE PRECISION array, dimension (LDA,N) On entry, the M-by-N matrix A. On exit, the elements on and above the diagonal of the array contain the min(M,N)-by-N upper trapezoidal matrix R (R is upper triangular if m >= n); the elements below the diagonal, with the array TAU, represent the orthogonal matrix Q as a product of min(m,n) elementary reflectors (see Further Details). |
|
lda |
LDA is INTEGER The leading dimension of the array A. LDA >= max(1,M). |
|
tau |
TAU is DOUBLE PRECISION array, dimension (min(M,N)) The scalar factors of the elementary reflectors (see Further Details). |
|
ws |
ncm_lapack_dgeqlf ()
gint ncm_lapack_dgeqlf (gint m
,gint n
,gdouble *a
,gint lda
,gdouble *tau
,NcmLapackWS *ws
);
DGEQLF computes a QL factorization of a real M-by-N matrix A: A = Q * L.
Parameters
m |
M is INTEGER The number of rows of the matrix A. M >= 0. |
|
n |
N is INTEGER The number of columns of the matrix A. N >= 0. |
|
a |
A is DOUBLE PRECISION array, dimension (LDA,N) On entry, the M-by-N matrix A. On exit, the elements on and above the diagonal of the array contain the min(M,N)-by-N upper trapezoidal matrix R (R is upper triangular if m >= n); the elements below the diagonal, with the array TAU, represent the orthogonal matrix Q as a product of min(m,n) elementary reflectors (see Further Details). |
|
lda |
LDA is INTEGER The leading dimension of the array A. LDA >= max(1,M). |
|
tau |
TAU is DOUBLE PRECISION array, dimension (min(M,N)) The scalar factors of the elementary reflectors (see Further Details). |
|
ws |
ncm_lapack_dgelqf ()
gint ncm_lapack_dgelqf (gint m
,gint n
,gdouble *a
,gint lda
,gdouble *tau
,NcmLapackWS *ws
);
DGELQF computes a LQ factorization of a real M-by-N matrix A: A = L * Q.
Parameters
m |
M is INTEGER The number of rows of the matrix A. M >= 0. |
|
n |
N is INTEGER The number of columns of the matrix A. N >= 0. |
|
a |
A is DOUBLE PRECISION array, dimension (LDA,N) On entry, the M-by-N matrix A. On exit, the elements on and above the diagonal of the array contain the min(M,N)-by-N upper trapezoidal matrix R (R is upper triangular if m >= n); the elements below the diagonal, with the array TAU, represent the orthogonal matrix Q as a product of min(m,n) elementary reflectors (see Further Details). |
|
lda |
LDA is INTEGER The leading dimension of the array A. LDA >= max(1,M). |
|
tau |
TAU is DOUBLE PRECISION array, dimension (min(M,N)) The scalar factors of the elementary reflectors (see Further Details). |
|
ws |
ncm_lapack_dggglm_alloc ()
GArray * ncm_lapack_dggglm_alloc (NcmMatrix *L
,NcmMatrix *X
,NcmVector *p
,NcmVector *d
,NcmVector *y
);
Calculates and allocs memory to solve the system determined by the parameters.
This function is expect the matrix X
and L
to be row-major.
ncm_lapack_dggglm_run ()
gint ncm_lapack_dggglm_run (GArray *ws
,NcmMatrix *L
,NcmMatrix *X
,NcmVector *p
,NcmVector *d
,NcmVector *y
);
Runs the dggglm function using the workspace ws
.
This function is expect the matrix X
and L
to be row-major.
ncm_lapack_dgels ()
gint ncm_lapack_dgels (gchar trans
,const gint m
,const gint n
,const gint nrhs
,gdouble *a
,const gint lda
,gdouble *b
,const gint ldb
,double *work
,const gint lwork
);
DGELS solves overdetermined or underdetermined real linear systems involving an M-by-N matrix A, or its transpose, using a QR or LQ factorization of A. It is assumed that A has full rank.
The following options are provided:
If TRANS = 'N' and m >= n: find the least squares solution of an overdetermined system, i.e., solve the least squares problem minimize || B - A*X ||.
If TRANS = 'N' and m < n: find the minimum norm solution of an underdetermined system A * X = B.
If TRANS = 'T' and m >= n: find the minimum norm solution of an underdetermined system A**T * X = B.
If TRANS = 'T' and m < n: find the least squares solution of an overdetermined system, i.e., solve the least squares problem minimize || B - A**T * X ||.
Several right hand side vectors b and solution vectors x can be handled in a single call; they are stored as the columns of the M-by-NRHS right hand side matrix B and the N-by-NRHS solution matrix X.
Parameters
trans |
is a char = 'N': the linear system involves A = 'T': the linear system involves A**T |
|
m |
is an integer. The number of rows of the matrix A. M >= 0 |
|
n |
is an integer. The number of columns of the matrix A. N >= 0 |
|
nrhs |
is an integer. The number of right hand sides, i.e., the number of columns of the matrices B and X. NRHS >=0 |
|
a |
array of doubles with dimension ( |
|
lda |
The leading dimension of the array |
|
b |
array of doubles with dimension ( |
|
ldb |
The leading dimension of the array |
|
work |
WORK is DOUBLE PRECISION array, dimension (4*N) |
|
lwork |
LWORK is INTEGER |
ncm_lapack_dgelsd ()
gint ncm_lapack_dgelsd (const gint m
,const gint n
,const gint nrhs
,gdouble *a
,const gint lda
,gdouble *b
,const gint ldb
,gdouble *s
,gdouble *rcond
,gint *rank
,NcmLapackWS *ws
);
DGELSD computes the minimum-norm solution to a real linear least squares problem: minimize 2-norm(| b - A*x |) using the singular value decomposition (SVD) of A. A is an M-by-N matrix which may be rank-deficient.
Several right hand side vectors b and solution vectors x can be handled in a single call; they are stored as the columns of the M-by-NRHS right hand side matrix B and the N-by-NRHS solution matrix X.
The problem is solved in three steps: (1) Reduce the coefficient matrix A to bidiagonal form with Householder transformations, reducing the original problem into a "bidiagonal least squares problem" (BLS) (2) Solve the BLS using a divide and conquer approach. (3) Apply back all the Householder transformations to solve the original least squares problem.
The effective rank of A is determined by treating as zero those singular values which are less than RCOND times the largest singular value.
The divide and conquer algorithm makes very mild assumptions about floating point arithmetic. It will work on machines with a guard digit in add/subtract, or on those binary machines without guard digits which subtract like the Cray X-MP, Cray Y-MP, Cray C-90, or Cray-2. It could conceivably fail on hexadecimal or decimal machines without guard digits, but we know of none.
Parameters
m |
is an integer. The number of rows of the matrix A. M >= 0 |
|
n |
is an integer. The number of columns of the matrix A. N >= 0 |
|
nrhs |
is an integer. The number of right hand sides, i.e., the number of columns of the matrices B and X. NRHS >=0 |
|
a |
array of doubles with dimension ( |
|
lda |
The leading dimension of the array |
|
b |
array of doubles with dimension ( |
|
ldb |
The leading dimension of the array |
|
s |
S is DOUBLE PRECISION array, dimension (min(M,N)) The singular values of A in decreasing order. The condition number of A in the 2-norm = S(1)/S(min(m,n)). |
|
rcond |
RCOND is DOUBLE PRECISION RCOND is used to determine the effective rank of A. Singular values S(i) <= RCOND*S(1) are treated as zero. If RCOND < 0, machine precision is used instead. |
|
rank |
RANK is INTEGER The effective rank of A, i.e., the number of singular values which are greater than RCOND*S(1). |
|
ws |
a Lapack workspace object NcmLapackWS |


"""
This module reads and writes CSV files to save/load the training data.
Project : Bomberman Bot with Machine Learning
Olin College Software Design Final Orject, Spring 2017
By : TEAM AFK
"""
import csv
[docs]def writeHead(fileName):
'''
Inserts the header into csv file.
'''
with open(fileName, newline='') as csvfile:
reader = csv.reader(csvfile, quotechar='|')
numrows = 0
for row in reader:
numrows += 1
print(numrows)
with open(fileName, 'a') as csvfile:
# record the number of training data
fieldnames = [str(numrows - 1)]
writer = csv.DictWriter(csvfile, fieldnames=fieldnames)
writer.writeheader()
[docs]def addRow(fileName, listInfo):
'''
Adds a new row to the csv.
'''
with open(fileName, 'a') as csvfile:
writer = csv.writer(csvfile,
quotechar='|', quoting=csv.QUOTE_MINIMAL)
writer.writerow(listInfo)
[docs]def readCSV(fileName):
"""
Loads the CSV file with the given filename
"""
with open('names.csv', newline='') as csvfile:
spamreader = csv.reader(csvfile, delimiter=' ', quotechar='|')
for row in spamreader:
print(', '.join(row))
[docs]def rewrite(fileName):
"""
Overwrites the CSV file with the given filename
"""
with open(fileName, 'w') as csvfile:
writer = csv.DictWriter(csvfile, fieldnames=[])
writer.writeheader()


Our clients range from entrepreneurs, high-profile individuals, to significant wealth-holders. We assist them in their daily and lifestyle management requirements. From planning your next holiday to a corporate event on a yacht, our expert luxury concierge and lifestyle management team will provide exceptional service.